Monotonicity Constraints in Characterizations of PSPACE
Amir M. Ben-Amram, Bruno Loff, Isabel Oitavem · Journal of Logic and Computation · 2010
A celebrated contribution of Bellantoni and Cook was a function algebra to capture FPTIME. This algebra uses recursion on notation. Later, Oitavem showed that including primitive recursion, an algebra is obtained that captures FPSPACE. The main results of this article concern variants of the later algebra. First, we show that iteration can replace primitive recursion. Then, we consider the results of imposing a monotonicity constraint on the primitive recursion or iteration. We find that in the case of iteration, the power of the algebra shrinks to FPTIME. More interestingly, with primitive recursion, we obtain a new implicit characterization of the polynomial hierarchy (FPH). The idea to consider these monotonicity constraints arose from the results on write-once tapes for Turing machines. We review this background and also note a new machine characterization of ΔP2, that similarly to our function algebras, arises by combining monotonicity constraints with a known characterization of PSPACE.