Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/8975

Generalized Hex and logical characterizations of polynomial space
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
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.
Peer Reviewed
À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
info:eu-repo/semantics/publishedVersion
Article
         

Mostra el registre complet del document

Documents relacionats

Altres documents del mateix autor/a

Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Ortiz Gómez, Carlos