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
id I19-R120-10915-50177
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
relational complexity
third order logic
expressibility of logics
relational machines
fixed point quantifiers
spellingShingle Ciencias Informáticas
relational complexity
third order logic
expressibility of logics
relational machines
fixed point quantifiers
Turull Torres, José María
Capturing relational NEXPTIME with a fragment of existential third order logic
topic_facet Ciencias Informáticas
relational complexity
third order logic
expressibility of logics
relational machines
fixed point quantifiers
description 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>.
format Articulo
Articulo
author Turull Torres, José María
author_facet Turull Torres, José María
author_sort Turull Torres, José María
title Capturing relational NEXPTIME with a fragment of existential third order logic
title_short Capturing relational NEXPTIME with a fragment of existential third order logic
title_full Capturing relational NEXPTIME with a fragment of existential third order logic
title_fullStr Capturing relational NEXPTIME with a fragment of existential third order logic
title_full_unstemmed Capturing relational NEXPTIME with a fragment of existential third order logic
title_sort capturing relational nexptime with a fragment of existential third order logic
publishDate 2015
url http://sedici.unlp.edu.ar/handle/10915/50177
http://journal.info.unlp.edu.ar/wp-content/uploads/JCST41-Paper-7.pdf
work_keys_str_mv AT turulltorresjosemaria capturingrelationalnexptimewithafragmentofexistentialthirdorderlogic
bdutipo_str Repositorios
_version_ 1764820475553251328

Ejemplares similares