Characterising space complexity classes via Knuth-Bendix orders

DOI10.1007/978-3-642-16242-8_11MaRDI QIDQ4933302zbMATH OpenOpenAlexFDO

Authors Guillaume Bonfante, Georg Moser

Publication date 12 October 2010

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16242-8_11

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42)

Recommendations

• KBOs, ordinals, subrecursive hierarchies and all that
• Derivational Complexity of Knuth-Bendix Orders Revisited
• An upper bound on the derivational complexity of Knuth-Bendix orderings.
• scientific article; zbMATH DE number 5722524
• scientific article; zbMATH DE number 1342224

Cited in

(2)

• Small term reachability and related problems for terminating term rewriting systems
• On the complexity of the small term reachability problem for terminating term rewriting systems

This page was built for publication: Characterising space complexity classes via Knuth-Bendix orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933302)