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

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

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.1007/s001530050054

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,590

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

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. [REVIEW]Karl-Heinz Niggl - 2000 - Bulletin of Symbolic Logic 6 (3):351-353.
A term rewriting characterization of the functions computable in polynomial space.Isabel Oitavem - 2002 - Archive for Mathematical Logic 41 (1):35-47.
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.
Deciding confluence of certain term rewriting systems in polynomial time.Guillem Godoy, Ashish Tiwari & Rakesh Verma - 2004 - Annals of Pure and Applied Logic 130 (1-3):33-59.
Characterizing PSPACE with pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
A characterization of the [mathematical formula]-definable functions of [mathematical formula].Wolfgang Burr & Volker Hartung - 1997 - Archive for Mathematical Logic 36 (3).
Papers by S. Bellantoni and S. Cook and by A. Beckmann and A. Weiermann.Karl-Heinz Niggl - 2000 - Bulletin of Symbolic Logic 6 (3):351-352.
Characterizing PSPACE with pointers.Isabel Oitavern - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
A logic of abstraction related to finite constructive number classes.Andrea Cantini - 1991 - Archive for Mathematical Logic 31 (1):69-83.
Andreas Weiermann. An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions. Discrete Mathematics and Theoretical Computer Science, vol. 6 no. 1 , pp. 133–141. [REVIEW]Albert A. Mullin - 2005 - Bulletin of Symbolic Logic 11 (1):89-89.

Analytics

Added to PP
2013-12-01

Downloads
43 (#110,248)

6 months
10 (#1,198,792)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

A lexicographic path order with slow growing derivation bounds.Naohi Eguchi - 2009 - Mathematical Logic Quarterly 55 (2):212-224.
2004 Summer Meeting of the Association for Symbolic Logic.Wolfram Pohlers - 2005 - Bulletin of Symbolic Logic 11 (2):249-312.

Add more citations

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.

Add more references