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>,ω</sup> of the third or- der logic TO<sup>ω</sup> captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines can simulate third order rel...

Descripción completa

Detalles Bibliográficos
Autor principal: Turull Torres, José María
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2015
Materias:
Ciencias Informáticas
relational machines
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/50424
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-50424
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 machines
spellingShingle Ciencias Informáticas
relational machines
Turull Torres, José María
Capturing relational NEXPTIME with a fragment of existential third order logic
topic_facet Ciencias Informáticas
relational machines
description We prove that the existential fragment Σ²<sub>1</sub><sup>,ω</sup> of the third or- der logic TO<sup>ω</sup> captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines can simulate third order relational machines.
format Objeto de conferencia
Objeto de conferencia
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/50424
work_keys_str_mv AT turulltorresjosemaria capturingrelationalnexptimewithafragmentofexistentialthirdorderlogic
bdutipo_str Repositorios
_version_ 1764820475016380416

Ejemplares similares