Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.ufpe.br/handle/123456789/1300
Title: Caracterização aritmética em primeira ordem de funções computáveis em espaço polinomial
Authors: Felix Lopes da Silva, Emmanuel
Keywords: Complexidade computacional; Aritmética; Fragmentos; PSPACE
Issue Date: 31-Jan-2008
Publisher: Universidade Federal de Pernambuco
Citation: 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.
Abstract: 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
URI: https://repositorio.ufpe.br/handle/123456789/1300
Appears in Collections:Teses de Doutorado - Ciência da Computação

Files in This Item:
File Description SizeFormat 
EFLS.pdf563.41 kBAdobe PDFView/Open


This item is protected by original copyright



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.