SOME FRAGMENTS OF SECOND-ORDER LOGIC OVER THE REALS FOR WHICH SATISFIABILITY AND EQUIVALENCE ARE (UN)DECIDABLE

• Authors: Rafael Grimson , Bart Kuijpers
• Languages of publication: PL

Abstracts

PL

We consider the 10-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 semialgebraic sets. We show that, in this context, satisability of formulas is decidable for the rst-order 9-quantier fragment and undecidable for the 98- and 8-fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas.

Keywords

PL

• Publisher: [unknown2]
• Journal: Reports on Mathematical Logic
• Year: 2014
• Volume: 49

Dates

published

2014

online

07 - 07 - 2015

Contributors

author

Rafael Grimson

author

Bart Kuijpers