{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:33:47Z","timestamp":1725456827990},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633860"},{"type":"electronic","value":"9783540695295"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0036180","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T07:47:22Z","timestamp":1134287242000},"page":"157-167","source":"Crossref","is-referenced-by-count":2,"title":["Logics which capture complexity classes over the reals"],"prefix":"10.1007","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":"297","published-online":{"date-parts":[[2005,6,21]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I and II. EATCS Monographs on Theoretical Computer Science, 11 and 22. Springer-Verlag, 1988, 1990.","DOI":"10.1007\/978-3-642-75357-2"},{"key":"13_CR2","unstructured":"L. Blum, F. Cuclcer, M. Shub, and S. Smale. Complexity and Real Computation. Springer Verlag, to appear."},{"key":"13_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc., 21:1\u201346, 1989.","journal-title":"Bulletin of the Amer. Math. Soc."},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"A. Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6:733\u2013744, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/0885-064X(92)90024-6","volume":"8","author":"F. Cucker","year":"1992","unstructured":"F. Cucker. P\u2260R \u2260 NC\u2260R. Journal of Complexity, 8:230\u2013238, 1992.","journal-title":"Journal of Complexity"},{"key":"13_CR6","unstructured":"F. Cucker and M. Matamala. On digital nondeterminism. To appear in Mathematical Systems Theory."},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1016\/0885-064X(92)90008-Y","volume":"8","author":"F. Cucker","year":"1992","unstructured":"F. Cucker and A. Torrecillas. Two P-complete problems in the theory of the reals. Journal of Complexity, 8:454\u2013466, 1992.","journal-title":"Journal of Complexity"},{"key":"13_CR8","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. SIAM-AMS Proc., 7:43\u201373, 1974.","journal-title":"SIAM-AMS Proc."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del and Y. Gurevich. Metafinite model theory. In: D. Leivant (ed.), Logic and Computational Complexity, pages 313\u2013366, Springer 1996","DOI":"10.1007\/3-540-60178-3_92"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del and K. Meer. Descriptive complexity theory over the real numbers. In J. Renegar, M. Shub, and S. Smale, editors, The Mathematics of Numerical Analysis, volume 32 of Lectures in Applied Mathematics, pages 381\u2013404. American Mathematical Society, 1996. A preliminary version appeared at STOC'95.","DOI":"10.1145\/225058.225151"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86\u2013104, 1986.","journal-title":"Information and Control"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM Journal on Computing, 16:760\u2013778, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(94)00070-0","volume":"133","author":"K. Meer","year":"1994","unstructured":"K. Meer. On the complexity of quadratic programming in real number models of computation. Theoretical Computer Science, 133:85\u201394, 1994.","journal-title":"Theoretical Computer Science"},{"key":"13_CR14","first-page":"113","volume":"4","author":"K. Meer","year":"1997","unstructured":"K. Meer and C. Michaux. A survey on real structural complexity theory. In Bulletin of the Belgian Math. Soc., 4:113\u2013148, 1997.","journal-title":"Bulletin of the Belgian Math. Soc."},{"issue":"1","key":"13_CR15","first-page":"435","volume":"309","author":"C. Michaux","year":"1989","unstructured":"C. Michaux. Une remarque \u00e0 propos des machines sur R introduites par Blum, Shub et Smale. C. R. Acad. Sci. Paris, 309, S\u00e9rie 1:435\u2013437, 1989.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"13_CR16","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0747-7171(10)80004-5","volume":"13","author":"J. Renegar","year":"1992","unstructured":"J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part II. Journal of Symbolic Computation, 13:301\u2013327, 1992.","journal-title":"Journal of Symbolic Computation"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"M. Vardi. Complexity of relational query languages. In 14th annual ACM Symp. on the Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0036180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T13:53:43Z","timestamp":1586613223000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0036180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633860","9783540695295"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0036180","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}