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, where tier 1 pointers were used or full parameter substitution over tier 0 was allowed. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim).

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 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. (shrink)

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 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. (shrink)