Characterizing PSPACE with pointers
โ
Isabel Oitavem
๐
Article
๐
2008
๐
John Wiley and Sons
๐
English
โ 124 KB
## 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 thi