Characterizing PSPACE with pointers

• Published in: Mathematical Logic Quarterly
• Main Author: Oitavem, Isabel
• Other Authors: UNL, CMAF, FCT
• Format: Article in Journal/Newspaper
• Language: English
• Published: Wiley 2008
• Subjects: The Pointers
• Online Access: http://dx.doi.org/10.1002/malq.200610056; https://api.wiley.com/onlinelibrary/tdm/v1/articles/10.1002%2Fmalq.200610056; https://onlinelibrary.wiley.com/doi/pdf/10.1002/malq.200610056

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)