GENERALIZED HEX AND LOGICAL CHARACTERIZATIONS OF POLYNOMIAL SPACE

Authors
ARRATIAQUESADA AA STEWART IA
Citation
Aa. Arratiaquesada et Ia. Stewart, GENERALIZED HEX AND LOGICAL CHARACTERIZATIONS OF POLYNOMIAL SPACE, Information processing letters, 63(3), 1997, pp. 147-152
Citations number
17
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
63
Issue
3
Year of publication
1997
Pages
147 - 152
Database
ISI
SICI code
0020-0190(1997)63:3<147:GHALCO>2.0.ZU;2-5
Abstract
We extend a logical characterization of PSPACE due to Makowsky and Pnu eli by showing that their logic has a particular normal form which imp lies that the Generalized Hex problem is complete for PSPACE via very restricted logical reductions. We also show that this normal form resu lt fails in the absence of a built-in successor relation. (C) 1997 Els evier Science B.V.