Generalized Hex and logical characterizations of polynomial space

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

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

dc.contributor	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
dc.contributor.author	Arratia Quesada, Argimiro Alejandro
dc.contributor.author	Stewart, Iain A.
dc.date	1997
dc.identifier.citation	Arratia, A.; Stewart, I. Generalized Hex and logical characterizations of polynomial space. "Information processing letters", 1997, vol. 63, núm. 3, p. 147-152.
dc.identifier.citation	0020-0190
dc.identifier.uri	http://hdl.handle.net/2117/8975
dc.language.iso	eng
dc.relation	http://www.lsi.upc.edu/~argimiro/mypapers/Journals/ipl97.pdf
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica::Mètodes en elements finits
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
dc.subject	Computational complexity
dc.subject	Finite element method
dc.subject	Complexitat computacional
dc.subject	Elements finits, Mètode dels
dc.title	Generalized Hex and logical characterizations of polynomial space
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/article
dc.description.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.
dc.description.abstract	Peer Reviewed

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

On the power of deep pushdown stacks

Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.

A note on first-order projections and games

Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.

Embedding in law of discrete time ARMA processes in continuous time stationary processes

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

American and exotic options in a market with frictions

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

A graphical tool for describing the temporal evolution of clusters in financial stock markets

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

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio