Characterizing PSPACE with pointers

Mathematical Logic Quarterly 54 (3):323-329 (2008)
  Copy   BIBTEX

Abstract

This paper gives an implicit characterization of the class of functions computable in polynomial space by deterministic Turing machines – PSPACE. It gives an inductive characterization of PSPACE with no ad-hoc initial functions and with only one recursion scheme. The main novelty of this characterization is the use of pointers to reach PSPACE. The presence of the pointers in the recursion on notation scheme is the main difference between this characterization of PSPACE and the well-known Bellantoni-Cook characterization of the polytime functions – PTIME.

Categories

Keywords

Reprint years

DOI

10.1002/malq.200610056

Other Versions

No versions found

Links

PhilArchive

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

Characterizing PSPACE with pointers.Isabel Oitavern - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
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.Karl-Heinz Niggl - 2000 - Bulletin of Symbolic Logic 6 (3):351-353.
Characterizing NC with tier 0 pointers.Isabel Oitavem - 2004 - Mathematical Logic Quarterly 50 (1):9.
Characterizing NC with tier 0 pointers.Isabel Oitavern - 2004 - Mathematical Logic Quarterly 50 (1):9-17.
Every polynomial-time 1-degree collapses if and only if P = PSPACE.Stephen A. Fenner, Stuart A. Kurtz & James S. Royer - 2004 - Journal of Symbolic Logic 69 (3):713-741.
Implicit recursion-theoretic characterizations of counting classes.Ugo Dal Lago, Reinhard Kahle & Isabel Oitavem - 2022 - Archive for Mathematical Logic 61 (7):1129-1144.
A term rewriting characterization of the functions computable in polynomial space.Isabel Oitavem - 2002 - Archive for Mathematical Logic 41 (1):35-47.
Modal Logics with Weak Forms of Recursion: PSPACE Specimens.Stéphane Demri - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev, Advances in Modal Logic. CSLI Publications. pp. 113-138.
Elementary arithmetic.Geoffrey E. Ostrin & Stanley S. Wainer - 2005 - Annals of Pure and Applied Logic 133 (1):275-292.
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.

Analytics

Added to PP
2013-12-01

Downloads
267 (#157,354)

6 months
29 (#328,585)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Weak Theories of Operations and Types.Thomas Strahm - 2010 - In Ralf Schindler, Ways of Proof Theory. Berlin, Boston: De Gruyter. pp. 441-468.
A recursion-theoretic approach to NP.Isabel Oitavem - 2011 - Annals of Pure and Applied Logic 162 (8):661-666.
Logspace without Bounds.Isabel Oitavem - 2010 - In Ralf Schindler, Ways of Proof Theory. Berlin, Boston: De Gruyter. pp. 355-362.

Add more citations

References found in this work

The Intrinsic Computational Difficulty of Functions.Alan Cobham - 1965 - In Yehoshua Bar-Hillel, Logic, methodology and philosophy of science. Amsterdam: North-Holland Pub. Co.. pp. 24-30.
Characterizing NC with tier 0 pointers.Isabel Oitavem - 2004 - Mathematical Logic Quarterly 50 (1):9.
Characterizing NC with tier 0 pointers.Isabel Oitavern - 2004 - Mathematical Logic Quarterly 50 (1):9-17.

Add more references