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

Bellantoni Cook schemata of predicative recursionderivation lengthsexponential timepolynomial time computable functionspredicative parameter substitutionterm rewriting

Mathematics Subject Classification ID

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

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

(13)

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

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)