A term rewriting characterization of the polytime functions and related complexity classes

DOI10.1007/S001530050054MaRDI QIDQ1354329zbMATH OpenOpenAlexFDO

Authors Arnold Beckmann, Andreas Weiermann

Publication date 2 June 1997

Published in Archive for Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

term rewritingexponential timederivation lengthspolynomial time computable functionsBellantoni Cook schemata of predicative recursionpredicative parameter substitution

Mathematics Subject Classification ID

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

Recommendations

• A term rewriting characterization of the functions computable in polynomial space
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• A lexicographic path order with slow growing derivation bounds
• scientific article; zbMATH DE number 1342224

Cited in

(11)

• A lexicographic path order with slow growing derivation bounds
• A term rewriting characterization of the functions computable in polynomial space
• Proving consistency of equational theories in bounded arithmetic
• Complexity Analysis by Rewriting
• How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study
• Closing the gap between runtime complexity and polytime computability
• On basic feasible functionals and the interpretation method
• A new order-theoretic characterisation of the polytime computable functions
• 2004 Summer Meeting of the Association for Symbolic Logic
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Complexity analysis of precedence terminating infinite graph rewrite systems

This page was built for publication: A term rewriting characterization of the polytime functions and related complexity classes

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