2010 | OriginalPaper | Buchkapitel
Characterising Space Complexity Classes via Knuth-Bendix Orders
verfasst von : Guillaume Bonfante, Georg Moser
Erschienen in: Logic for Programming, Artificial Intelligence, and Reasoning
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study three different space complexity classes:
LINSPACE
,
PSPACE
, and
ESPACE
and give complete characterisations for these classes. We employ rewrite systems, whose termination can be shown by Knuth Bendix orders. To capture
LINSPACE
, we consider positively weighted Knuth Bendix orders. To capture
PSPACE
, we consider unary rewrite systems, compatible with a Knuth Bendix order, where we allow for padding of the input. And to capture
ESPACE
, we make use of a non-standard generalisation of the Knuth Bendix order.