Characterizing PSPACE with pointers
Mathematical Logic Quarterly · 2008-06 · 54 (3) · 323-329
DOI: 10.1002/malq.200610056 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Logic Quarterly, online erschienen am 06.05.2008. Verfasst von Isabel Oitavem. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 11 Literaturangaben. Gefördert von: UNL, CMAF, FCT.
Abstract (Originalsprache)
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)
Förderung
- UNL
- CMAF
- FCT
Zitieren
APA
Oitavem, I. (2008). Characterizing PSPACE with pointers. Mathematical Logic Quarterly, 54(3), 323-329. https://doi.org/10.1002/malq.200610056
Vancouver
Oitavem I. Characterizing PSPACE with pointers. Mathematical Logic Quarterly. 2008;54(3):323-329. doi:10.1002/malq.200610056
BibTeX
@article{Oitavem2008,
author = {Oitavem, Isabel},
title = {Characterizing PSPACE with pointers},
journal = {Mathematical Logic Quarterly},
year = {2008},
volume = {54},
number = {3},
pages = {323--329},
doi = {10.1002/malq.200610056}
}
EUVIMED