Characterising Space Complexity Classes via Knuth-Bendix Orders

Guillaume Bonfante 1 Georg Moser 2
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this paper we study three different space complexity classes: LINSPACE, PSPACE, and ESPACE, which are commonly believed to be distinct. We give complete characterisations of these classes exploiting rewrite systems, whose termination can be shown by Knuth-Bendix orders. To capture LINSPACE, we consider positively weighted systems. To capture PSPACE, we consider unary rewrite systems, where we allow for padding of the input. And to capture ESPACE, we make use of a variant of the Knuth-Bendix order, induced by quasi-precedences.
Type de document :
Communication dans un congrès
Christian G. Fermüller and Andrei Voronkov. 17th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning - LPAR-17, Oct 2010, Yogyakarta, Indonesia. Springer, 6397, pp.142--156, 2010, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00535541
Contributeur : Guillaume Bonfante <>
Soumis le : jeudi 11 novembre 2010 - 14:27:45
Dernière modification le : mardi 24 avril 2018 - 13:33:45

Identifiants

  • HAL Id : inria-00535541, version 1

Collections

Citation

Guillaume Bonfante, Georg Moser. Characterising Space Complexity Classes via Knuth-Bendix Orders. Christian G. Fermüller and Andrei Voronkov. 17th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning - LPAR-17, Oct 2010, Yogyakarta, Indonesia. Springer, 6397, pp.142--156, 2010, Lecture Notes in Computer Science. 〈inria-00535541〉

Partager

Métriques

Consultations de la notice

202