Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/18538
Title: | Some fragments of second-order logic over the reals for which satisability and equivalence are (un)decidable | Authors: | GRIMSON, Rafael KUIJPERS, Bart |
Issue Date: | 2014 | Source: | Reports on Mathematical Logic, 49, p. 23-34 | Abstract: | We consider the \Sigma_0^1-fragment of second-order logic over the vocabulary ⟨+, ×, 0, 1, <, S_1, ..., S_k⟩, interpreted over the reals, where the predicate symbols S_i are interpreted as semi- algebraic sets. We show that, in this context, satisfiability of formulas is decidable for the first-order \exists^\ast-quantifier fragment and undecidable for the \exists^\ast\forall- and \forall^\ast-fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas. | Notes: | E-mail Addresses:rgrimson@unsam.edu.ar | Keywords: | logic; second-order logic; satisfiability; equivalence; containment; decision problem | Document URI: | http://hdl.handle.net/1942/18538 | Link to publication/dataset: | http://rml.tcs.uj.edu.pl/rml-49/2-grimson.pdf | ISSN: | 0137-2904 | e-ISSN: | 0137-2904 | DOI: | 10.4467/20842589RM.14.002.2272 | ISI #: | 000342408200002 | Rights: | Jagiellonian University, Krakow, Poland | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2016 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RML-2014-grimson-kuijpers.pdf | Published version | 273.27 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.