cl-banner

Characterising Space Complexity Classes via Knuth-Bendix Orders

Guillaume Bonfante and Georg Moser

Proceedings of the 17th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-17), Lecture Notes in Computer Science (Advanced Research in Computing and Software Science) 6397, pp. 142 – 156, 2010.

Abstract

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.

 

  PDF |    doi:10.1007/978-3-642-16242-8_11  |  © Springer

BibTeX 

@inproceedings{GBGM-LPAR17,
author = "Guillaume Bonfante and Georg Moser",
title = "Characterising Space Complexity Classes via {Knuth-Bendix} Orders",
booktitle = "Proceedings of the 17th International Conference on Logic
for Programming, Artificial Intelligence, and Reasoning",
series = "Lecture Notes in Computer Science (Advanced Research in
Computing and Software Science)",
volume = 6397,
pages = "142--156",
year = 2010
}
Nach oben scrollen