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


A.A. Arratia


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.


Arratia, A., & Stewart, I. (2003). A note on first-order projections and games. Theoretical Computer Science, 290(3), 2085-2093.

Journal Article Type Article
Publication Date Jan 1, 2003
Deposit Date Jun 29, 2009
Publicly Available Date Aug 25, 2009
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 290
Issue 3
Pages 2085-2093
Keywords Descriptive complexity, Finite model theory, Quantifier-free projections.
Publisher URL


You might also like

Downloadable Citations