Capturing relational NEXPTIME with a fragment of existential third order logic
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>...
Guardado en:
| Autor principal: | Turull Torres, José María |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2015
|
| Materias: | |
| 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: |
Ejemplares similares
-
Capturing relational NEXPTIME with a fragment of existential third order logic
por: Turull Torres, José María
Publicado: (2015) -
Quantifiers in language and logic
por: Peters, Stanley, 1941-
Publicado: (2006) -
Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
por: Figueira, S., et al. -
Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
por: Figueira, Santiago Daniel, et al.
Publicado: (2014) -
Swap logic
por: Areces, Carlos Eduardo, et al.
Publicado: (2021)