Saltar para:
Logótipo
Comuta visibilidade da coluna esquerda
Você está em: Início > Publicações > Visualização > Monotonicity Constraints in Characterizations of PSPACE

Publicações

Monotonicity Constraints in Characterizations of PSPACE

Título
Monotonicity Constraints in Characterizations of PSPACE
Tipo
Artigo em Revista Científica Internacional
Ano
2012
Autores
Ben Amram, AM
(Autor)
Outra
A pessoa não pertence à instituição. A pessoa não pertence à instituição. A pessoa não pertence à instituição. Sem AUTHENTICUS Sem ORCID
Loff, B
(Autor)
Outra
Oitavem, I
(Autor)
Outra
A pessoa não pertence à instituição. A pessoa não pertence à instituição. A pessoa não pertence à instituição. Ver página do Authenticus Sem ORCID
Revista
Vol. 22
Páginas: 179-195
ISSN: 0955-792X
Outras Informações
ID Authenticus: P-005-GRQ
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
Documentos
Não foi encontrado nenhum documento associado à publicação.
Publicações Relacionadas

Da mesma revista

On long normal inhabitants of a type (2005)
Artigo em Revista Científica Internacional
Broda, S; Damas, L
Linearity in Computation (2014)
Artigo em Revista Científica Internacional
Florido, M; Mackie, I
Linearity: A Roadmap (2014)
Artigo em Revista Científica Internacional
Sandra Alves; Maribel Fernandez; Mario Florido; Ian Mackie
Recomendar Página Voltar ao Topo
Copyright 1996-2025 © Faculdade de Direito da Universidade do Porto  I Termos e Condições  I Acessibilidade  I Índice A-Z
Página gerada em: 2025-09-02 às 17:40:53 | Política de Privacidade | Política de Proteção de Dados Pessoais | Denúncias