Switch to: References

Citations of:

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

Arnold Beckmann & Andreas Weiermann

Archive for Mathematical Logic 36 (1):11-30 (1996)

Add citations

You must login to add citations.

A lexicographic path order with slow growing derivation bounds.Naohi Eguchi - 2009 - Mathematical Logic Quarterly 55 (2):212-224.details This paper is concerned with implicit computational complexity of the exptime computable functions. Modifying the lexicographic path order, we introduce a path order EPO. It is shown that a termination proof for a term rewriting system via EPO implies an exponential bound on the lengths of derivations. The path order EPO is designed so that every exptime function is representable as a term rewrite system compatible with EPO (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). Download Export citation Bookmark
(1 other version)How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study.Andreas Weiermann - 1998 - Journal of Symbolic Logic 63 (4):1348-1370.details Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε 0 -recursive function [] 0 : T → ω so that a reduces to b implies [a] $_0 > [b]_0$ . The construction of [] 0 is based on a careful analysis of the Howard-Schütte (...) Download Export citation Bookmark 7 citations
(1 other version)Proving consistency of equational theories in bounded arithmetic.Arnold Beckmann† - 2002 - Journal of Symbolic Logic 67 (1):279-296.details We consider equational theories for functions defined via recursion involving equations between closed terms with natural rules based on recursive definitions of the function symbols. We show that consistency of such equational theories can be proved in the weak fragment of arithmetic S 1 2 . In particular this solves an open problem formulated by TAKEUTI (c.f. [5, p.5 problem 9.]). Download Export citation Bookmark 1 citation
2004 Summer Meeting of the Association for Symbolic Logic.Wolfram Pohlers - 2005 - Bulletin of Symbolic Logic 11 (2):249-312.details Download Export citation Bookmark

1