Skip Navigation

Logic Journal of IGPL 2002 10(2):105-122; doi:10.1093/jigpal/10.2.105
© 2002 by Oxford University Press
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Arratia, A.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Original Article

On the Descriptive Complexity of a Simplified Game of Hex

Argimiro Arratia

Departamento de Matemáticas, Universidad Simón Bolívar, Apartado 89000, Caracas 1080-A, Venezuela. E-mail: arratia{at}ma.usb.ve

The game Whex is here defined, which is similar to Generalized Hex but the players are restricted to colour vertices adjacent to the vertex last coloured by one of the players. It is shown that the problem of deciding existence of winning strategies for one of the players in this game is complete for PSPACE, via quantifier free projections, and that the extension of first order logic with the corresponding generalized quantifier captures PSPACE and verifies a normal form. This problem is used to show that the problem of finding a proof in a proof system, like propositional resolution, in which the user is allowed to introduce auxiliary statements in order to help the system reach the theorem that he had set it to prove, is also complete for PSPACE via quantifier free projections. Also, it is established the complexity of the game Whex when restricted to graphs of outdegree at most 3, and, as a generalized quantifier, its expressive capabilities in the absence of ordering relation.

Key Words: Descriptive complexity; generalized quantifier; quantifier free projection; games; Generalized Hex; polynomial space

Received 21 March, 2002.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.