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

DOI10.1007/S001530050054zbMath0941.03040OpenAlexW2075296484MaRDI QIDQ1354329

Andreas Weiermann, Arnold Beckmann

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 of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (5)

How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study ⋮ Proving consistency of equational theories in bounded arithmetic ⋮ 2004 Summer Meeting of the Association for Symbolic Logic ⋮ Complexity Analysis by Rewriting ⋮ A lexicographic path order with slow growing derivation bounds

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