To access the full text documents, please follow this link: http://hdl.handle.net/2117/8975

Title:	Generalized Hex and logical characterizations of polynomial space
Author:	Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Other authors:	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
Abstract:	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.
Abstract:	Peer Reviewed
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica::Mètodes en elements finits -Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat -Computational complexity -Finite element method -Complexitat computacional -Elements finits, Mètode dels
Rights:
Document type:	Article - Published version Article
Share:

Show full item record