Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Hasselt University | |
| dc.contributor.author | Grimson, Rafael | |
| dc.contributor.author | Kuijpers, Bart | |
| dc.date.issued | 2014-05 | |
| dc.description.abstract | We consider the Σ1 0-fragment of second-order logic over the vocabulary h+, ×, 0, 1, <, S1, ..., Ski, interpreted over the reals, where the predicate symbols Si are interpreted as semi-algebraic sets. We show that, in this context, satisfiability of formulas is decidable for the first-order ∃ ∗ - quantifier fragment and undecidable for the ∃ ∗∀- and ∀ ∗ -fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas. | es |
| dc.description.fil | Fil: Grimson, Rafael. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Kuijpers, Bart. Hasselt University; Bélgica | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Grimson, Rafael; Kuijpers, Bart; Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable; Jagiellonian University; Reports on Mathematical Logic; 49; 5-2014; 23-34 | es |
| dc.identifier.eissn | 2084-2589 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0137-2904 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/35394 | |
| dc.journal.pagination | 23-34 | es |
| dc.journal.pais | Polonia | es |
| dc.journal.title | Reports on Mathematical Logic | es |
| dc.journal.volume | 49 | es |
| dc.language.iso | eng | es |
| dc.publisher | Jagiellonian University | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.ejournals.eu/rml/2014/Numer-49/art/3576/ | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | Logic | es |
| dc.subject | Decidability | es |
| dc.subject | Finite Models | es |
| dc.subject.classification | Matemática Pura | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.5a3f9afa-a75a-4d9b-b1b0-edb7be1e9a81_A.pdf
- Tamaño:
- 307.77 KB
- Formato:
- Adobe Portable Document Format