Monotonicity Constraints in Characterizations of PSPACE

• Tipo: Artigo em Revista Científica Internacional
• Data: 2012

Autores

Ben Amram, AM (Autor) Outra; Loff, B (Autor) Outra; Oitavem, I (Autor) Outra

Revista

Título: Journal of Logic and Computation

Vol. 22

Páginas: 179-195

ISSN: 0955-792X

Editora: Oxford University Press

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 17