{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:27:39Z","timestamp":1773228459375,"version":"3.50.1"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":5490,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1999,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NC<jats:sub>\u211d<\/jats:sub>, PAR<jats:sub>\u211d<\/jats:sub>, EXP<jats:sub>\u211d<\/jats:sub> and some others more.<\/jats:p>","DOI":"10.2307\/2586770","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:02:25Z","timestamp":1146938545000},"page":"363-390","source":"Crossref","is-referenced-by-count":16,"title":["Logics which capture complexity classes over the reals"],"prefix":"10.1017","volume":"64","author":[{"given":"Felipe","family":"Cucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Meer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200014092_ref010","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1995"},{"key":"S0022481200014092_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF01301968"},{"key":"S0022481200014092_ref015","unstructured":"Gross D. , Comptage sur les nombres r\u00e9els, preprint. 1997."},{"key":"S0022481200014092_ref005","doi-asserted-by":"publisher","DOI":"10.1137\/0206054"},{"key":"S0022481200014092_ref011","first-page":"43\u201373","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","volume":"7","author":"Fagin","year":"1974","journal-title":"SIAM-AMS Proceedings"},{"key":"S0022481200014092_ref007","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.5.400"},{"key":"S0022481200014092_ref022","volume-title":"Computational complexity","author":"Papadimitriou","year":"1994"},{"key":"S0022481200014092_ref024","first-page":"301\u2013327","article-title":"On the computational complexity and geometry of the first-order theory of the reals. Part II","volume":"13","author":"Renegar","year":"1992","journal-title":"Journal of Symbolic Computation"},{"key":"S0022481200014092_ref025","first-page":"137\u2013146","author":"Vardi","year":"1982","journal-title":"14th ACM symposium on the theory of computing"},{"key":"S0022481200014092_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97062-7"},{"key":"S0022481200014092_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(92)90008-Y"},{"key":"S0022481200014092_ref004","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"S0022481200014092_ref012","first-page":"952\u2013969","volume":"60","author":"Gr\u00e4del","year":"1995","journal-title":"Tailoring recursion for complexity"},{"key":"S0022481200014092_ref020","first-page":"113\u2013148","article-title":"A survey on real structural complexity theory","volume":"4","author":"Meer","year":"1996","journal-title":"Bulletin of the Belgian Mathematical Society"},{"key":"S0022481200014092_ref019","first-page":"398","volume-title":"Proceedings of the 22nd international symposium on mathematical foundations of computer science, bratislava","volume":"1295","author":"Meer","year":"1997"},{"key":"S0022481200014092_ref006","first-page":"230\u2013238","article-title":"P\u211d \u2260 NC\u211d","volume":"8","author":"Cucker","year":"1992","journal-title":"Journal of Complexity"},{"key":"S0022481200014092_ref023","first-page":"255\u2013299","article-title":"On the computational complexity and geometry of the first-order theory of the reals. Part I","volume":"13","author":"Renegar","year":"1992","journal-title":"Journal of Symbolic Computation"},{"key":"S0022481200014092_ref013","first-page":"313\u2013366","volume-title":"Logic and computational complexity","author":"Gr\u00e4del","year":"1996"},{"key":"S0022481200014092_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00070-0"},{"key":"S0022481200014092_ref017","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"S0022481200014092_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"S0022481200014092_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-75357-2"},{"key":"S0022481200014092_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"S0022481200014092_ref021","first-page":"435\u2013437","article-title":"Une remarque \u00e0 propos \u00e0 des machines sur \u211d introduites par Blum, Shub et Smale","volume":"309","author":"Michaux","year":"1989","journal-title":"Comptes Rendus de l\u2019Acad\u00e9mie des Sciences Paris"},{"key":"S0022481200014092_ref014","first-page":"381\u2013404","volume-title":"The mathematics of numerical analysis","volume":"32","author":"Gr\u00e4del","year":"1996"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200014092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T19:07:26Z","timestamp":1557515246000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200014092\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,3]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1999,3]]}},"alternative-id":["S0022481200014092"],"URL":"https:\/\/doi.org\/10.2307\/2586770","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,3]]}}}