Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Generalized Hex and logical characterizations of polynomial space

Autor
Arratia, A.; Stewart, I.
Tipus d'activitat
Article en revista
Revista
Information processing letters
Data de publicació
1997
Volum
63
Número
3
Pàgina inicial
147
Pàgina final
152
Repositori
http://hdl.handle.net/2117/8975 Obrir en finestra nova
URL
http://www.lsi.upc.edu/~argimiro/mypapers/Journals/ipl97.pdf Obrir en finestra nova
Resum
We extend a logical characterization of PSPACE due to Makowsky and Pnueli by showing that their logic has a particular normal form which implies that the Generalized Hex problem is complete for PSPACE via very restricted logical reductions. We also show that this normal form result fails in the absence of a built-in successor relation.
Citació
Arratia, A.; Stewart, I. Generalized Hex and logical characterizations of polynomial space. "Information processing letters", 1997, vol. 63, núm. 3, p. 147-152.

Participants