Pspace
Mostrando 1-2 de 2 artigos, teses e dissertações.
-
1. Complexidade descritiva das lÃgicas de ordem superior com menor ponto fixo e anÃlise de expressividade de algumas lÃgicas modais / Descriptive complexity of the logic of higher order with lower fixed point and analysis of expression of some modal logics
Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela logica existencial de segunda-ordem, considerado o primeiro resultado da area, outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados mais conhecid
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia. Publicado em: 13/08/2010
-
2. CaracterizaÃÃo aritmÃtica em primeira ordem de funÃÃes computÃveis em espaÃo polinomial
In this work, we develop a characterization of the polynomial space computable functions in the rst order theory of binary strings. We prove a analogous result to Parikh`s Theorem on the polynomial bound on the growth size of de nable functions. This work is a natural extension of Prof. Fernando Ferreira`s system of polynomial time computable arit
Publicado em: 2008