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.accessRightsOpen Access-
item.contributorGRIMSON, Rafael-
item.contributorKUIJPERS, Bart-
item.validationecoom 2016-
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

Google ScholarTM

Check

Altmetric


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