Artículos de revistas
Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable
Fecha
2014-05Registro en:
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
0137-2904
2084-2589
CONICET Digital
CONICET
Autor
Grimson, Rafael
Kuijpers, Bart
Resumen
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.