A carregar...
Publicação
Bounded theories for polyspace computability
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 129.15 KB | Adobe PDF |
Orientador(es)
Resumo(s)
We present theories of bounded arithmetic and weak analysis whose provably total functions
(with appropriate graphs) are the polyspace computable functions. More precisely, inspired in
Ferreira’s systems PTCA, Sigma^b_1-NIA and BTFA in the polytime framework, we propose analogue theories
concerning polyspace computability. Since the techniques we employ in the characterization of
PSPACE via formal systems (e.g. Herbrand’s theorem, cut-elimination theorem and the expansion
of models) are similar to the ones involved in the polytime setting, we focus on what is specific of
polyspace and explains the lift from PTIME to PSPACE.
Descrição
Palavras-chave
Bounded arithmetic Weak analysis Polyspace computability Conservation results