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

Description

Made available in DSpace on 2014-06-12T15:48:52Z (GMT). No. of bitstreams: 1
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2008 / 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

Links & Downloads

1. 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.
2. https://repositorio.ufpe.br/handle/123456789/1300

Tags

Complexidade computacional

Aritmética

Fragmentos

PSPACE

Additional Fields

Identifer	oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/1300
Date	31 January 2008
Creators	Felix Lopes da Silva, Emmanuel
Contributors	José Guerra Barreto de Queiroz, Ruy
Publisher	Universidade Federal de Pernambuco
Source Sets	IBICT Brazilian ETDs
Language	Portuguese
Detected Language	Portuguese
Type	info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Source	reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE
Rights	info:eu-repo/semantics/openAccess