doctoralThesis
Caracterização aritmética em primeira ordem de funções computáveis em espaço polinomial
Registro en:
Felix Lopes da Silva, Emmanuel; José Guerra Barreto de Queiroz, Ruy. Caracterização aritmética em primeira ordem de funções computáveis em espaço polinomial. 2008. Tese (Doutorado). Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Pernambuco, Recife, 2008.
Autor
Felix Lopes da Silva, Emmanuel
Institución
Resumen
Nesta tese desenvolvemos uma caracterização das funções computáveis em espaço
polinomial por meio da lógica de primeira ordem de seqüência binárias. Provamos,
também, um resultado análogo ao Teorema de Parikh sobre limitação polinomial
no tamanho de crescimento das funções de…níveis em tal sistema. Este trabalho é
uma extensão natural do sistema desenvolvido pelo Professor Fernando Ferreira da
Universidade de Lisboa, que trata das funções computáveis em tempo polinomial