Generalized Hex and logical characterizations of polynomial space

Argimiro A. Arratia-Quesada, Iain A. Stewart

We answer a question posed by Makowsky and Pnueli and show that the logic $(\pm\mbox{HEX})^\ast[\mbox{FO}_s]$, where HEX is the operator (i.e., uniform sequence of Lindström quanti…