The Existential Fragment of Third Order Logic and Third Order Relational Machines
We introduce a new sub logic of third order logic (TO), the logic TOϖ, as a semantic restriction of TO. We focus on the existential fragment of TOϖ which we denote Σ²ϖ , and we study its relational complexity by introducing a variation of the non deterministic relational machine, which we denote 3-...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2014
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/42242 |
| Aporte de: |
| Sumario: | We introduce a new sub logic of third order logic (TO), the logic TOϖ, as a semantic restriction of TO. We focus on the existential fragment of TOϖ which we denote Σ²ϖ , and we study its relational complexity by introducing a variation of the non deterministic relational machine, which we denote 3-NRM, where we allow third order relations in the relational store of the machine.We then prove that Σ²ϖ characterizes exactly NEXPTIME3,r |
|---|