Generalized Hex and logical characterizations of polynomial space

Finite model theory. Logical characterizations of polynomial space. Completeness via logical reductions. We consider a particular logical characterization of the complexity class PSPACE using first-order logic, with a built-in successor relation, extended 1 Partially supported by EPSRC Grant GR/K 96564. 2 Most of this work was done whilst the author was visiting the University of Leicester. with an operator corresponding to the well-known PSPACE-complete decision problem Generalized Hex; that is, the logic (\SigmaHEX) [FO s ]. It was shown by Makowsky and Pnueli [12] (see also [11]) that any problem in PSPACE can be defined by a sentence of the logic (\SigmaHEX) [FO s ], and, conversely, that any problem definable by a sentence of this logic is in PSPACE. There are numerous other simila