- Tytuł:
- Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable
- Autorzy:
-
Grimson, Rafael
Kuijpers, Bart - Powiązania:
- https://bibliotekanauki.pl/articles/1368654.pdf
- Data publikacji:
- 2014
- Wydawca:
- Uniwersytet Jagielloński. Wydawnictwo Uniwersytetu Jagiellońskiego
- Opis:
- We consider the $\Sigma_0^1$-fragment of second-order logic over the vocabulary $\langle+, \times, 0, 1, <, S_1, ..., S_k \rangle$, interpreted over the reals, where the predicate symbols $S_i$ are interpreted as semialgebraic sets. We show that, in this context, satisability of formulas is decidable for the first-order $\exists$*-quantifier fragment and undecidable for the $\exists$*$\forall$- and $\forall$*-fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas.
- Źródło:
-
Reports on Mathematical Logic; 2014, 49; 23-34
0137-2904
2084-2589 - Pojawia się w:
- Reports on Mathematical Logic
- Dostawca treści:
- Biblioteka Nauki
Artykuł