A term rewriting characterization of the functions computable in polynomial space

Archive for Mathematical Logic 41 (1):35-47 (2002)
  Copy   BIBTEX

Abstract

We give a term rewriting characterization of the polyspace functions. Our work follows investigations on term rewriting characterizations of some classes of (sub-) recursive functions as initiated by Cichon and Weiermann [4] and continued by Beckmann and Weiermann [1].The main novelty of this paper is a technique for reformulating recursion schemes. The aim of this technique is to provide rewriting rules which give rise to rewriting chains whose terms are suitably bounded. This bounding is crucial when dealing with computational classes with space constraints.

Categories

Keywords

Reprint years

DOI

10.1007/s001530200002

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,676

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 polytime functions and related complexity classes.Arnold Beckmann & Andreas Weiermann - 1996 - Archive for Mathematical Logic 36 (1):11-30.
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.
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.
A lexicographic path order with slow growing derivation bounds.Naohi Eguchi - 2009 - Mathematical Logic Quarterly 55 (2):212-224.
Bounded iteration and unary functions.Stefano Mazzanti - 2005 - Mathematical Logic Quarterly 51 (1):89-94.
Strictly orthogonal left linear rewrite systems and primitive recursion.E. A. Cichon & E. Tahhan-Bittar - 2001 - Annals of Pure and Applied Logic 108 (1-3):79-101.
Characterizing PSPACE with pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Term rewriting theory for the primitive recursive functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
Thue trees.Jerzy Marcinkowski & Leszek Pacholski - 2003 - Annals of Pure and Applied Logic 119 (1-3):19-59.

Analytics

Added to PP
2013-11-23

Downloads
17 (#1,145,417)

6 months
4 (#1,244,521)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

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