A term rewriting characterization of the polytime functions and related complexity classes
Archive for Mathematical Logic 36 (1):11-30 (1996)
Abstract
This article has no associated abstract. (fix it)DOI
10.1007/s001530050054
My notes
Similar books and articles
A term rewriting characterization of the functions computable in polynomial space.Isabel Oitavem - 2002 - Archive for Mathematical Logic 41 (1):35-47.
Term rewriting theory for the primitive recursive functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
Subrecursive functions on partial sequences.Karl-Heinz Niggl - 1999 - Archive for Mathematical Logic 38 (3):163-193.
The $\mu$ -measure as a tool for classifying computational complexity.Karl-Heinz Niggl - 2000 - Archive for Mathematical Logic 39 (7):515-539.
Tailoring recursion for complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Termination and confluence in infinitary term rewriting.P. H. Rodenburg - 1998 - Journal of Symbolic Logic 63 (4):1286-1296.
Logics which capture complexity classes over the reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
A lexicographic path order with slow growing derivation bounds.Naohi Eguchi - 2009 - Mathematical Logic Quarterly 55 (2):212-224.
Truth definitions in finite models.Leszek Aleksander Kołodziejczyk - 2004 - Journal of Symbolic Logic 69 (1):183-200.
Types of I -free hereditary right maximal terms.Katalin Bimbó - 2005 - Journal of Philosophical Logic 34 (5/6):607 - 620.
Some Hierarchies of Primitive Recursive Functions on Term Algebras.Klaus-Hilmar Sprenger - 1997 - Mathematical Logic Quarterly 43 (2):251-286.
Analytics
Added to PP
2013-12-01
Downloads
31 (#379,464)
6 months
1 (#452,962)
2013-12-01
Downloads
31 (#379,464)
6 months
1 (#452,962)
Historical graph of downloads
Citations of this work
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.
2004 Summer Meeting of the Association for Symbolic Logic.Wolfram Pohlers - 2005 - Bulletin of Symbolic Logic 11 (2):249-312.
A lexicographic path order with slow growing derivation bounds.Naohi Eguchi - 2009 - Mathematical Logic Quarterly 55 (2):212-224.
Proving consistency of equational theories in bounded arithmetic.Arnold Beckmann† - 2002 - Journal of Symbolic Logic 67 (1):279-296.
References found in this work
The realm of primitive recursion.Harold Simmons - 1988 - Archive for Mathematical Logic 27 (2):177-188.
Term rewriting theory for the primitive recursive functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
A proof of strongly uniform termination for Gödel's $T$ by methods from local predicativity.Andreas Weiermann - 1997 - Archive for Mathematical Logic 36 (6):445-460.
