A lexicographic path order with slow growing derivation bounds

DOI10.1002/malq.200710090zbMath1171.03023arXiv1201.0562OpenAlexW2093899660MaRDI QIDQ3619873

Naohi Eguchi

Publication date: 9 April 2009

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.0562

zbMATH Keywords

term rewritingfunction algebrarecursion-theoretic characterizations of complexity classessafe recursion on notation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• A new recursion-theoretic characterization of the polytime functions
• A term rewriting characterization of the polytime functions and related complexity classes
• Proof-theoretic analysis of termination proofs
• A new function algebra of EXPTIME functions by safe nested recursion
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: A lexicographic path order with slow growing derivation bounds