In this paper we focus on the class of functions computable in deterministic polynomial space -Pspace. Our aim is to give a survey on implicit characterizations of Pspace. Special attention will be given to characterizations where no bounded recursion scheme is invoked and within them to term rewriting characterizations.
展开▼