Complexity classes and rewrite systems with polynomial interpretation

DOI10.1007/10703163_25MaRDI QIDQ4263809zbMATH OpenFDO

Authors Guillaume Bonfante, A. Cichon, Jean-Yves Marion, H. Touzet

Publication date 22 September 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10703163_25

zbMATH Keywords

computable functionsfeasible computationrewrite systemtermination orderings

Mathematics Subject Classification ID

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

Recommendations

• Algorithms with polynomial interpretation termination proof
• Polynomial interpretations and the complexity of algorithms
• A term rewriting characterization of the polytime functions and related complexity classes
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• A term rewriting characterization of the functions computable in polynomial space

Cited in

(16)

• A term rewriting characterization of the polytime functions and related complexity classes
• A term rewriting characterization of the functions computable in polynomial space
• Relative undecidability in term rewriting. I: The termination hierarchy
• Relative undecidability in term rewriting. II: The confluence hierarchy
• Applications and extensions of context-sensitive rewriting
• Derivational complexity and context-sensitive Rewriting
• Characterizing polynomial time complexity of stream programs using interpretations
• On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting
• Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
• Polygraphic programs and polynomial-time functions
• Polynomial interpretations and the complexity of algorithms
• Characterising space complexity classes via Knuth-Bendix orders
• scientific article; zbMATH DE number 2201367 (Why is no real title available?)
• Closing the gap between runtime complexity and polytime computability
• scientific article; zbMATH DE number 5499325 (Why is no real title available?)
• A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations

This page was built for publication: Complexity classes and rewrite systems with polynomial interpretation

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