Carregant...
Carregant...

Vés al contingut (premeu Retorn)

A note on first-order projections and games

Autor
Arratia, A.; Stewart, I.
Tipus d'activitat
Article en revista
Revista
Theoretical computer science
Data de publicació
2003
Volum
290
Número
3
Pàgina inicial
2085
Pàgina final
2093
DOI
https://doi.org/10.1016/S0304-3975(02)00491-7 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/9005 Obrir en finestra nova
URL
http://www.lsi.upc.edu/~argimiro/mypapers/Journals/FOProjGames.pdf Obrir en finestra nova
Resum
We show how the fact that there is a first-order projection with successor from the problem TC (transitive clousure) to some other problem Ω enables us to automatically deduce that a natural game problem, LGΩ, whose instances are labelled instances of Ω is complete for PSPACE (via log-space reductions). Our analysis is strongly dependent upon the reduction from TC to Ω being a logical projection in that it fails should the reduction be, for example, a log-space reduction or a quantifier-...
Citació
Arratia, A.; Stewart, I. A note on first-order projections and games. "Theoretical computer science (Berlin, west)", 2003, vol. 290, núm. 3, p. 2085-2093.

Participants

Arxius