Capturing relational NEXPTIME with a fragment of existential third order logic

Mostrar todas las versiones(2)

We prove that the existential fragment Σ<sub>1</sub><sup>2,ω</sup> of the third order logic TO<sup>ω</sup> captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines that work in NEXPTIME<sub>...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Turull Torres, José María
Formato:	Articulo
Lenguaje:	Inglés
Publicado:	2015
Materias:	Ciencias Informáticas relational complexity third order logic expressibility of logics relational machines fixed point quantifiers
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/50177 http://journal.info.unlp.edu.ar/wp-content/uploads/JCST41-Paper-7.pdf
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

Descripción
Sumario:	We prove that the existential fragment Σ<sub>1</sub><sup>2,ω</sup> of the third order logic TO<sup>ω</sup> captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines that work in NEXPTIME<sub>r</sub> can simulate third order relational machines that work in NEXPTIME<sub>3,r</sub>.