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 |
Page view(s)
22
checked on Sep 7, 2022
Download(s)
32
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.