Monotonicity Constraints in Characterizations of PSPACE

• Type: Article in International Scientific Journal
• Date: 2012

Authors

Ben Amram, AM (Author) Other; Loff, B (Author) Other; Oitavem, I (Author) Other

Journal

Title: Journal of Logic and Computation

Vol. 22

Pages: 179-195

ISSN: 0955-792X

Publisher: Oxford University Press

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 1 Citation

Other information

Authenticus ID: P-005-GRQ

DOI: 10.1093/logcom/exq002

Abstract (EN): 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 delta(P)(2), that similarly to our function algebras, arises by combining monotonicity constraints with a known characterization of PSPACE.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 17