Caracterização aritmética em primeira ordem de funções computáveis em espaço polinomial

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

Grantor dc:publisher

Universidade Federal de Pernambuco

Year dc:date.issued

2008

Author dc:creator

• Felix Lopes da Silva, Emmanuel

Advisor dc:contributor.advisor

• José Guerra Barreto de Queiroz, Ruy

• Complexidade computacional
• Aritmética
• Fragmentos
• PSPACE

Statement dc:rights

• openAccess
• Attribution-NonCommercial-NoDerivs 3.0 Brazil

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc-nd/3.0/br/

Language dc:language.iso

por

Repository record dc:identifier.uri

https://repositorio.ufpe.br/handle/123456789/1300

OAI identifier oai:identifier

oai:repositorio.ufpe.br:123456789/1300