Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of the polytime functions. Computational complexity, vol. 2 , pp. 97–110. - Arnold Beckmann and Andreas Weiermann. A term rewriting characterization of the polytime functions and related complexity classes. Archive for mathematical logic, vol. 36 , pp. 11–30 [Book Review]

Bulletin of Symbolic Logic 6 (3):351-353 (2000)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.2307/421064

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

A term rewriting characterization of the polytime functions and related complexity classes.Arnold Beckmann & Andreas Weiermann - 1996 - Archive for Mathematical Logic 36 (1):11-30.
Elementary arithmetic.Geoffrey E. Ostrin & Stanley S. Wainer - 2005 - Annals of Pure and Applied Logic 133 (1):275-292.
Characterizing PSPACE with pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Characterizing PSPACE with pointers.Isabel Oitavern - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Andreas Weiermann. Complexity bounds for some finite forms of Kruskal's Theorem. Journal of Symbolic Computation, vol. 18 , pp. 463–448. - Andreas Weiermann. Termination proofs for term rewriting systems with lexicographic path ordering imply multiply recursive derivation lengths. Theoretical Computer Science, vol. 139 , pp. 355–362. - Andreas Weiermann. Bounding derivation lengths with functions from the slow growing hierarchy. Archive of Mathematical Logic, vol. 37 , pp. 427–441. [REVIEW]Georg Moser - 2004 - Bulletin of Symbolic Logic 10 (4):588-590.
The $\mu$ -measure as a tool for classifying computational complexity.Karl-Heinz Niggl - 2000 - Archive for Mathematical Logic 39 (7):515-539.
A uniform approach for characterizing the provably total number-theoretic functions of KPM and its subsystems.Benjamin Blankertz & Andreas Weiermann - 1999 - Studia Logica 62 (3):399-427.
Subrecursive functions on partial sequences.Karl-Heinz Niggl - 1999 - Archive for Mathematical Logic 38 (3):163-193.
Characterising polytime through higher type recursion.Stephen J. Bellantoni, Karl-Heinz Niggl & Helmut Schwichtenberg - 2000 - Annals of Pure and Applied Logic 104 (1-3):17-30.
An application of category-theoretic semantics to the characterisation of complexity classes using higher-order function algebras.Martin Hofmann - 1997 - Bulletin of Symbolic Logic 3 (4):469-486.
Quantified propositional calculus and a second-order theory for NC1.Stephen Cook & Tsuyoshi Morioka - 2005 - Archive for Mathematical Logic 44 (6):711-749.
A term rewriting characterization of the functions computable in polynomial space.Isabel Oitavem - 2002 - Archive for Mathematical Logic 41 (1):35-47.
Approximation to measurable functions and its relation to probabilistic computation.Ker-I. Ko - 1986 - Annals of Pure and Applied Logic 30 (2):173-200.
Term rewriting theory for the primitive recursive functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
An order-theoretic characterization of the Howard–Bachmann-hierarchy.Jeroen Van der Meeren, Michael Rathjen & Andreas Weiermann - 2017 - Archive for Mathematical Logic 56 (1-2):79-118.

Analytics

Added to PP
2013-11-21

Downloads
38 (#409,607)

6 months
4 (#790,687)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Safe recursion with higher types and BCK-algebra.Martin Hofmann - 2000 - Annals of Pure and Applied Logic 104 (1-3):113-166.
A verisimilitudinarian analysis of the Linda paradox.Gustavo Cevolani, Vincenzo Crupi & Roberto Festa - 2012 - VII Conference of the Spanish Society for Logic, Methodology and Philosphy of Science.
Elementary arithmetic.Geoffrey E. Ostrin & Stanley S. Wainer - 2005 - Annals of Pure and Applied Logic 133 (1):275-292.

View all 11 citations / Add more citations

References found in this work

No references found.

Add more references