Título:
|
A note on first-order projections and games
|
Autor/a:
|
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics |
Abstract:
|
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-free first-order translation with successor. |
Abstract:
|
Peer Reviewed |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica -Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Teoria de jocs -Game theory -Jocs, Teoria de |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión presentada Artículo |
Compartir:
|
|