{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:08:34Z","timestamp":1759147714645},"reference-count":37,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,2,1]],"date-time":"2003-02-01T00:00:00Z","timestamp":1044057600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3855,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,2]]},"DOI":"10.1016\/s0022-0000(02)00034-x","type":"journal-article","created":{"date-parts":[[2003,4,5]],"date-time":"2003-04-05T01:27:43Z","timestamp":1049506063000},"page":"169-206","source":"Crossref","is-referenced-by-count":13,"title":["Reachability and connectivity queries in constraint databases"],"prefix":"10.1016","volume":"66","author":[{"given":"Michael","family":"Benedikt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(02)00034-X_BIB1","series-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB2","doi-asserted-by":"crossref","unstructured":"F. Afrati, S. Cosmadakis, S. Grumbach, G. Kuper, Linear vs. polynomial constraints in database query languages, in: Proceedings of Conference on Principles and Practice of Constraint Programming, Springer, Berlin, 1994, pp. 181\u2013192.","DOI":"10.1007\/3-540-58601-6_100"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB3","series-title":"Real Algebraic and Semi-algebraic Sets","author":"Benedetti","year":"1990"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/273865.273870","article-title":"Relational expressive power of constraint query languages","volume":"45","author":"Benedikt","year":"1998","journal-title":"J. ACM"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB5","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1145\/347476.347477","article-title":"Relational queries over interpreted structures","volume":"47","author":"Benedikt","year":"2000","journal-title":"J. ACM"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB6","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0022-0000(86)90029-2","article-title":"The complexity of elementary algebra and geometry","volume":"32","author":"Ben-Or","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB7","series-title":"Real Algebraic Geometry","author":"Bochnak","year":"1998"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB8","doi-asserted-by":"crossref","unstructured":"B.F. Caviness, J.R. Johnson (Eds.), Quantifier Elimination and Cylindrical Algebraic Decomposition, Springer, Berlin, 1998.","DOI":"10.1007\/978-3-7091-9459-1"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB9","series-title":"Model Theory","author":"Chang","year":"1990"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB10","doi-asserted-by":"crossref","unstructured":"G.E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition, in: Automation Theory and Formal Languages, Lecture Notes in Computer Science, Vol. 33, Springer, Berlin, 1975, pp. 134\u2013183.","DOI":"10.1007\/3-540-07407-4_17"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB11","article-title":"Temporal and modal logic","volume":"Vol. B","author":"Emerson","year":"1990"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB12","unstructured":"F. Geerts, B. Kuijpers, Expressing topological connectivity of spatial databases, in: Database Programming Languages, Lecture Notes in Computer Science, Vol. 1949, Springer, Berlin, 1999, pp. 224\u2013238."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB13","doi-asserted-by":"crossref","unstructured":"F. Geerts, B. Kuijpers, Linear approximation of planar spatial databases using transitive-closure logic, in: ACM Symposium on Principles of Database Systems, ACM Press, New York, 2000, pp. 126\u2013135.","DOI":"10.1145\/335168.335215"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB14","unstructured":"C. Giannella, D. Van Gucht, Adding a path connectedness operator to FO+poly (linear), Technical Report, Indiana University, November 1999."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB15","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, S. Kreutzer, Descriptive complexity theory for constraint databases, in: Computer Science Logic, Springer Verlag, Berlin, 1999, pp. 67\u201381.","DOI":"10.1007\/3-540-48168-0_6"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB16","doi-asserted-by":"crossref","unstructured":"S. Grumbach, G. Kuper, Tractable recursion over geometric data, in: Constraint Programming 97, Lecture Notes in Computer Science, Vol. 1330, Springer, Berlin, 1997, pp. 450\u2013462.","DOI":"10.1007\/BFb0017459"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB17","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02573999","article-title":"Description of connected components of a semialgebraic set in single exponential time","volume":"11","author":"Heintz","year":"1994","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB18","doi-asserted-by":"crossref","unstructured":"T.A. Henzinger, The theory of hybrid automata, in: IEEE Symposium on Logic in Computer Science, IEEE Press, New York, 1996, pp. 278\u2013292.","DOI":"10.1109\/LICS.1996.561342"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB19","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","article-title":"Languages that capture complexity classes","volume":"16","author":"Immerman","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB20","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1006\/jcss.1995.1051","article-title":"Constraint query languages","volume":"51","author":"Kanellakis","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB21","doi-asserted-by":"crossref","unstructured":"S. Kreutzer, Fixed-point query languages for linear constraint databases, in: ACM Symposium on Principles of Database Systems, ACM Press, New York, 2000, pp. 116\u2013125.","DOI":"10.1145\/335168.335214"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB22","doi-asserted-by":"crossref","unstructured":"B. Kuijpers, J. Paredaens, J. Van den Bussche, On topological elementary equivalence of spatial databases, in: International Conference on Database Theory, Lecture Notes in Computer Science, Vol. 1186, Springer, Berlin, 1997, pp. 432\u2013446.","DOI":"10.1007\/3-540-62222-5_62"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB23","doi-asserted-by":"crossref","unstructured":"B. Kuijpers, M. Smits, On expressing topological connectivity in spatial datalog, in: Workshop on Constraint Databases, Springer Verlag, Berlin, 1997, pp. 116\u2013133.","DOI":"10.1007\/3-540-62501-1_29"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB24","doi-asserted-by":"crossref","unstructured":"B. Kuijpers, J. Van den Bussche, On capturing first-order topological properties of planar spatial databases, in: International Conference on Database Theory, Lecture Notes in Computer Science, Vol. 1540, Springer, Berlin, 1999, pp. 187\u2013198.","DOI":"10.1007\/3-540-49257-7_13"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB25","doi-asserted-by":"crossref","unstructured":"G. Kuper, L. Libkin, J. Paredaens (Eds.), Constraint Databases, Springer, Berlin, 2000.","DOI":"10.1007\/978-3-662-04031-7"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB26","doi-asserted-by":"crossref","unstructured":"G. Lafferriere, G. Pappas, S. Sastry, A new class of decidable hybrid systems, in: Hybrid Systems 1999, Lecture Notes in Computer Science, Vol. 1569, Springer, Berlin, 1999, pp. 137\u2013151.","DOI":"10.1007\/3-540-48983-5_15"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00009858","article-title":"O-minimal hybrid systems","volume":"13","author":"Lafferriere","year":"2000","journal-title":"Math. Control Signals Systems"},{"issue":"1","key":"10.1016\/S0022-0000(02)00034-X_BIB28","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1006\/jcss.1998.1597","article-title":"Topological queries in spatial databases","volume":"58","author":"Papadimitriou","year":"1999","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB29","doi-asserted-by":"crossref","first-page":"1747","DOI":"10.1137\/S009753979629766","article-title":"First-order queries on finite structures over the reals","volume":"27","author":"Paredaens","year":"1998","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB30","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1090\/S0002-9947-1988-0943306-9","article-title":"Definable sets in ordered structures. III","volume":"309","author":"Pillay","year":"1988","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB31","series-title":"Constraint Databases","first-page":"155","article-title":"Datalog and constraints","author":"Revesz","year":"2000"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB32","series-title":"Convex Analysis","author":"Rockafellar","year":"1970"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB33","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1006\/jcss.2000.1712","article-title":"Querying spatial databases via topological invariants","volume":"61","author":"Segoufin","year":"2000","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB34","series-title":"Convexity and Optimization in Finite Dimensions","author":"Stoer","year":"1970"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB35","series-title":"Tame Topology and O-minimal Structures","author":"van den Dries","year":"1998"},{"key":"10.1016\/S0022-0000(02)00034-X_BIB36","unstructured":"M.Y. Vardi, P. Wolper, An automata-theoretic approach to automatic program verification, in: IEEE Symposium on Logic in Computer Science, IEEE Press, New York, 1986, pp. 322\u2013331."},{"key":"10.1016\/S0022-0000(02)00034-X_BIB37","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1090\/S0894-0347-96-00216-0","article-title":"Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function","volume":"9","author":"Wilkie","year":"1996","journal-title":"J. Amer. Math. Soc."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S002200000200034X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S002200000200034X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T19:29:04Z","timestamp":1584473344000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S002200000200034X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,2]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,2]]}},"alternative-id":["S002200000200034X"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(02)00034-x","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,2]]}}}