Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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
URI: http://hdl.handle.net/1942/18538
Link to publication: http://rml.tcs.uj.edu.pl/rml-49/2-grimson.pdf
DOI: 10.4467/20842589RM.14.002.2272
ISI #: 000342408200002
ISSN: 0137-2904
Category: A1
Type: Journal Contribution
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published article273.27 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.