Skip to main content

Research Repository

Advanced Search

A note on first-order projections and games

Arratia, A.A.; Stewart, I.A.

A note on first-order projections and games Thumbnail


Authors

A.A. Arratia



Abstract

We show how the fact that there is a first-order projection from the problem TC (transitive closure) to some other problem $\Omega$ enables us to automatically deduce that a natural game problem, $\mathcal{LG}(\Omega)$, whose instances are labelled instances of $\Omega$, is complete for PSPACE (via log-space reductions). Our analysis is strongly dependent upon the reduction from TC to $\Omega$ 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.

Citation

Arratia, A., & Stewart, I. (2003). A note on first-order projections and games. Theoretical Computer Science, 290(3), 2085-2093. https://doi.org/10.1016/s0304-3975%2802%2900491-7

Journal Article Type Article
Publication Date Jan 1, 2003
Deposit Date Jun 29, 2009
Publicly Available Date Mar 28, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 290
Issue 3
Pages 2085-2093
DOI https://doi.org/10.1016/s0304-3975%2802%2900491-7
Keywords Descriptive complexity, Finite model theory, Quantifier-free projections.
Publisher URL http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V1G-47T5C4X-B-3&_cdi=5674&_user=121711&_orig=browse&_coverDate=01%2F03%2F2003&_sk=997099996&view=c&wchp=dGLbVzb-zSkWb&md5=18e079ca996a694d81fbeccd5897fb59&ie=/sdarticle.pdf

Files





You might also like



Downloadable Citations