EUVIMEDEUVIMED entdecken
Crossref

Characterizing PSPACE with pointers

Isabel Oitavem

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →