Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/18538
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GRIMSON, Rafael | - |
dc.contributor.author | KUIJPERS, Bart | - |
dc.date.accessioned | 2015-04-01T08:39:21Z | - |
dc.date.available | 2015-04-01T08:39:21Z | - |
dc.date.issued | 2014 | - |
dc.identifier.citation | Reports on Mathematical Logic, 49, p. 23-34 | - |
dc.identifier.issn | 0137-2904 | - |
dc.identifier.uri | http://hdl.handle.net/1942/18538 | - |
dc.description.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. | - |
dc.description.sponsorship | Research partially supported by the following Argentinian and Belgian grants: PICT 2012-2403 and FWO G.0344.05. | - |
dc.language.iso | en | - |
dc.rights | Jagiellonian University, Krakow, Poland | - |
dc.subject.other | logic; second-order logic; satisfiability; equivalence; containment; decision problem | - |
dc.title | Some fragments of second-order logic over the reals for which satisability and equivalence are (un)decidable | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 34 | - |
dc.identifier.spage | 23 | - |
dc.identifier.volume | 49 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | E-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.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | 10.4467/20842589RM.14.002.2272 | - |
dc.identifier.isi | 000342408200002 | - |
dc.identifier.url | http://rml.tcs.uj.edu.pl/rml-49/2-grimson.pdf | - |
item.validation | ecoom 2016 | - |
item.contributor | GRIMSON, Rafael | - |
item.contributor | KUIJPERS, Bart | - |
item.accessRights | Open Access | - |
item.fullcitation | GRIMSON, 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.fulltext | With Fulltext | - |
crisitem.journal.issn | 0137-2904 | - |
crisitem.journal.eissn | 0137-2904 | - |
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.