Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/18538
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGRIMSON, Rafael-
dc.contributor.authorKUIJPERS, Bart-
dc.date.accessioned2015-04-01T08:39:21Z-
dc.date.available2015-04-01T08:39:21Z-
dc.date.issued2014-
dc.identifier.citationReports on Mathematical Logic, 49, p. 23-34-
dc.identifier.issn0137-2904-
dc.identifier.urihttp://hdl.handle.net/1942/18538-
dc.description.abstractWe 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.-
dc.description.sponsorshipResearch partially supported by the following Argentinian and Belgian grants: PICT 2012-2403 and FWO G.0344.05.-
dc.language.isoen-
dc.rightsJagiellonian University, Krakow, Poland-
dc.subject.otherlogic; second-order logic; satisfiability; equivalence; containment; decision problem-
dc.titleSome fragments of second-order logic over the reals for which satisability and equivalence are (un)decidable-
dc.typeJournal Contribution-
dc.identifier.epage34-
dc.identifier.spage23-
dc.identifier.volume49-
local.bibliographicCitation.jcatA1-
dc.description.notesE-mail Addresses:rgrimson@unsam.edu.ar-
dc.relation.references[1] J. Bochnak, M. Coste, M.-F. Roy, Real Algebraic Geometry, Volume 36 of Ergebenisse der Mathematik und ihrer Grenzgebiete, Folge 3, Springer-Verlag, Berlin, 1998. [2] G. Jeronimo and J. Sabia, On the number of sets definable by polynomials, Journal Algebra 227:2 (2000), 633–644. [3] E.Borger,E.Gradel and Y.Gurevich,TheClassicalDecisionProblem,Monographs in Mathematical Logic, Springer-Verlag, 2000. [4] D. Grigoriev and N. N. (jr.) Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation 5 (1988), 37–64. [5] J. P. Jones and Y. V. Matijasevich, Exponential Diophantine representation of recursively enumerable sets, In J. Stern, editor, Proceedings of the Herbrand Sym- posium: Logic Colloquium ’81, volume 107 of Studies in Logic and the Foundations of Mathematics, Amsterdam. North Holland, 1982, pp.159–177. [6] Y. V. Matijasevich, Hilbert’s Tenth Problem, MIT Press, Cambridge, MA, 1993. [7] J. Paredaens, G. Kuper and L. Libkin, editors, Constraint databases, Springer- Verlag, 2000. [8] A. Tarski, A Decision Method for Elementary Algebra and Geometry, University of California Press, 1951.-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.identifier.doi10.4467/20842589RM.14.002.2272-
dc.identifier.isi000342408200002-
dc.identifier.urlhttp://rml.tcs.uj.edu.pl/rml-49/2-grimson.pdf-
item.validationecoom 2016-
item.contributorGRIMSON, Rafael-
item.contributorKUIJPERS, Bart-
item.accessRightsOpen Access-
item.fullcitationGRIMSON, Rafael & KUIJPERS, Bart (2014) Some fragments of second-order logic over the reals for which satisability and equivalence are (un)decidable. In: Reports on Mathematical Logic, 49, p. 23-34.-
item.fulltextWith Fulltext-
crisitem.journal.issn0137-2904-
crisitem.journal.eissn0137-2904-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
RML-2014-grimson-kuijpers.pdfPublished version273.27 kBAdobe PDFView/Open
Show simple item record

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.