𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterizing PSPACE with pointers

✍ Scribed by Isabel Oitavem

Book ID
102485099
Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
124 KB
Volume
54
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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 (also called path information) 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. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

📜 SIMILAR VOLUMES

Characterizing NC with tier 0 pointers
Characterizing NC with tier 0 pointers
✍ Isabel Oitavem 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB

## Abstract A two‐sorted term system characterizing __NC__ implicitly is described. The term system is defined over the tree algebra 𝕋, the free algebra generated by **0**, **1** and ∗︁, and the recursion scheme uses pointers over tier 0. This differs from previous characterizations of __NC__, wher

Calculating with pointers
Calculating with pointers
✍ A. Bijlsma 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 618 KB
IP = PSPACE
IP = PSPACE
✍ Shamir, Adi 📂 Article 📅 1992 🏛 Association for Computing Machinery 🌐 English ⚖ 548 KB
Phutball is PSPACE-hard
Phutball is PSPACE-hard
✍ Dariusz Dereniowski 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 386 KB