Generalized Hex and logical characterizations of polynomial space

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/8975

Título:	Generalized Hex and logical characterizations of polynomial space
Autor/a:	Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Otros autores:	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
Materia(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
Derechos:
Tipo de documento:	Artículo - Versión publicada Artículo
Compartir:

Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.

Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.

Arratia Quesada, Argimiro Alejandro; Cabaña, Ana Alejandra; Cabaña Perez, Enrique

Junike, Gero; Arratia Quesada, Argimiro Alejandro; Cabaña Nigro, Ana Alejandra; Schoutens, Wim

Arratia Quesada, Argimiro Alejandro; Cabaña, Ana Alejandra

Coordinación

Patrocinio