{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:05:54Z","timestamp":1761620754322},"reference-count":66,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2000,10,1]],"date-time":"2000-10-01T00:00:00Z","timestamp":970358400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":4680,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2000,10]]},"DOI":"10.1016\/s0004-3702(00)00055-2","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T16:57:34Z","timestamp":1027616254000},"page":"223-263","source":"Crossref","is-referenced-by-count":11,"title":["Querying temporal and spatial constraint networks in PTIME\u2606\u2606A preliminary version of this paper appeared in the proceedings of AAAI-99. A different version of this paper (aimed at a database audience) appeared in the proceedings of the workshop STDBM99."],"prefix":"10.1016","volume":"123","author":[{"given":"Manolis","family":"Koubarakis","sequence":"first","affiliation":[]},{"given":"Spiros","family":"Skiadopoulos","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/S0004-3702(00)00055-2_ID006","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0304-3975(51)90007-2","article-title":"On the representation and querying of sets of possible worlds","volume":"Vol. 78","author":"Abiteboul","year":"1991","journal-title":"Theoret. Comput. Sci."},{"issue":"11","key":"10.1016\/S0004-3702(00)00055-2_ID007","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","article-title":"Maintaining knowledge about temporal intervals","volume":"Vol. 26","author":"Allen","year":"1983","journal-title":"Comm. ACM"},{"key":"10.1016\/S0004-3702(00)00055-2_ID008","series-title":"Proc. 6th International Conference on the Principles of Knowledge Representation and Reasoning, Trento, Italy","article-title":"Bidimensional temporal relations","author":"Balbiani","year":"1998"},{"key":"10.1016\/S0004-3702(00)00055-2_ID009","series-title":"Proc. 8th International Symposium on Methodologies for Intelligent Systems","article-title":"LaTeR: A general purpose manager of temporal information","volume":"Vol. 869","author":"Brusoni","year":"1994"},{"key":"10.1016\/S0004-3702(00)00055-2_ID010","series-title":"Recent Advances in Temporal Databases (Proceedings of the International Workshop on Temporal Databases, Z\u00fcrich, Switzerland, September 1995)","article-title":"Extending temporal relational databases to deal with imprecise and qualitative temporal information","author":"Brusoni","year":"1995"},{"issue":"4","key":"10.1016\/S0004-3702(00)00055-2_ID011","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1109\/64.608197","article-title":"Later: An efficient, general purpose manager of temporal information","volume":"Vol. 12","author":"Brusoni","year":"1997","journal-title":"IEEE Expert"},{"issue":"2","key":"10.1016\/S0004-3702(00)00055-2_ID012","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0004-3702(95)00008-3","article-title":"On the computational complexity of querying bounds on differences constraints","volume":"Vol. 74","author":"Brusoni","year":"1995","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID013","series-title":"Proc. CP-97, Linz, Austria","first-page":"478","article-title":"Tractable disjunctive constraints","volume":"Vol. 1330","author":"Cohen","year":"1997"},{"key":"10.1016\/S0004-3702(00)00055-2_ID014","series-title":"Proc. VLDB-2000, Cairo, Egypt","article-title":"Temporal integrity constraints with indeterminacy","author":"Cowley","year":"2000"},{"key":"10.1016\/S0004-3702(00)00055-2_ID015","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0004-3702(88)90087-2","article-title":"Reasoning about partially ordered events","volume":"Vol. 36","author":"Dean","year":"1988","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID016","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0004-3702(92)90043-W","article-title":"From local to global consistency","volume":"Vol. 55","author":"Dechter","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID017","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90061-0","article-title":"Temporal data base management","volume":"Vol. 32","author":"Dean","year":"1987","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID018","series-title":"Proc. 1st International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ontario","first-page":"83","article-title":"Temporal constraint networks","author":"Dechter","year":"1989"},{"issue":"1\u20133","key":"10.1016\/S0004-3702(00)00055-2_ID019","first-page":"61","article-title":"Temporal constraint networks","volume":"Vol. 49","author":"Dechter","year":"1991","journal-title":"Artificial Intelligence (Special Volume on Knowledge Representation)"},{"issue":"1","key":"10.1016\/S0004-3702(00)00055-2_ID020","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","article-title":"Network-based heuristics for constraint satisfaction problems","volume":"Vol. 34","author":"Dechter","year":"1988","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID021","series-title":"A Mathematical Introduction to Logic","author":"Enderton","year":"1972"},{"issue":"1","key":"10.1016\/S0004-3702(00)00055-2_ID022","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","article-title":"A sufficient condition for backtrack-free search","volume":"Vol. 29","author":"Freuder","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(00)00055-2_ID023","series-title":"Reasoning with inequations in temporal constraint networks","author":"Gerevini","year":"1995"},{"key":"10.1016\/S0004-3702(00)00055-2_ID024","series-title":"Proc. IJCAI-97, Nagoya, Japan","first-page":"1460","article-title":"On finding a solution in temporal constraint satisfaction problems","author":"Gerevini","year":"1997"},{"issue":"1","key":"10.1016\/S0004-3702(00)00055-2_ID025","first-page":"45","article-title":"Constraint query algebras","volume":"Vol. 1","author":"Goldin","year":"1997","journal-title":"Constraints"},{"key":"10.1016\/S0004-3702(00)00055-2_ID026","series-title":"Constraint query algebras, Ph.D. Thesis","author":"Goldin","year":"1997"},{"key":"10.1016\/S0004-3702(00)00055-2_ID027","series-title":"The Problem of Incomplete Information in Relational Databases","volume":"Vol. 554","author":"Grahne","year":"1991"},{"key":"10.1016\/S0004-3702(00)00055-2_ID028","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0004-3702(94)90110-4","article-title":"On point-based temporal disjointness","volume":"Vol. 70","author":"Gerevini","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID029","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0004-3702(94)00016-T","article-title":"Efficient algorithms for qualitative reasoning about time","volume":"Vol. 74","author":"Gerevini","year":"1995","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID030","series-title":"Spatial reasoning based on Allen's temporal logic","author":"G\u00fcsgen","year":"1989"},{"issue":"4","key":"10.1016\/S0004-3702(00)00055-2_ID031","article-title":"An introduction to spatial database systems","volume":"Vol. 3","author":"G\u00fcting","year":"1994","journal-title":"The VLDB J. (Special Issue on Spatial Databases)"},{"key":"10.1016\/S0004-3702(00)00055-2_ID032","series-title":"Qualitative Representation of Spatial Knowledge","volume":"Vol. 804","author":"Hernandez","year":"1994"},{"issue":"6","key":"10.1016\/S0004-3702(00)00055-2_ID033","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1137\/S0097539793251876","article-title":"Simple and fast algorithms for linear and integer programs with two variables per inequality","volume":"Vol. 23","author":"Hochbaum","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0004-3702(00)00055-2_ID034","series-title":"Proc. Australian Computer Science Conference (Australian Computer Science Communications)","first-page":"102","article-title":"A unit two variable per inequality integer constraint solver for constraint logic programming","author":"Harvey","year":"1997"},{"issue":"4","key":"10.1016\/S0004-3702(00)00055-2_ID035","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/1634.1886","article-title":"Incomplete information in relational databases","volume":"Vol. 31","author":"Imielinski","year":"1984","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(00)00055-2_ID036","series-title":"Proc. AAAI-96, Portland, OR","first-page":"1235","article-title":"A linear programming approach to temporal reasoning","author":"Jonsson","year":"1996"},{"key":"10.1016\/S0004-3702(00)00055-2_ID037","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0004-3702(98)00031-9","article-title":"A unifying approach to temporal constraint reasoning","volume":"Vol. 102","author":"Jonsson","year":"1998","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID038","series-title":"Proc. PPCP-94","first-page":"86","article-title":"Beyond finite domains","volume":"Vol. 874","author":"Jaffar","year":"1994"},{"key":"10.1016\/S0004-3702(00)00055-2_ID039","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"Vol. 20","author":"Kachiyan","year":"1979","journal-title":"Soviet Mathematics Doklady"},{"key":"10.1016\/S0004-3702(00)00055-2_ID040","series-title":"Proc. 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","first-page":"299","article-title":"Constraint query languages","author":"Kanellakis","year":"1990"},{"key":"10.1016\/S0004-3702(00)00055-2_ID041","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1006\/jcss.1995.1051","article-title":"Constraint query languages","volume":"Vol. 51","author":"Kanellakis","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0004-3702(00)00055-2_ID042","series-title":"Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference (KR-92), Cambridge, MA","first-page":"24","article-title":"Dense time and temporal constraints with \u2260","author":"Koubarakis","year":"1992"},{"key":"10.1016\/S0004-3702(00)00055-2_ID043","series-title":"Proc. 1st International Conference on Principles and Practice of Constraint Programming (CP-95), Cassis, France","first-page":"53","article-title":"From local to global consistency in temporal constraint networks","volume":"Vol. 976","author":"Koubarakis","year":"1995"},{"key":"10.1016\/S0004-3702(00)00055-2_ID044","series-title":"Proceedings 2nd International Conference on Principles and Practice of Constraint Programming (CP-96), Boston, MA","first-page":"297","article-title":"Tractable disjunctions of linear constraints","author":"Koubarakis","year":"1996"},{"key":"10.1016\/S0004-3702(00)00055-2_ID045","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/S0304-3975(96)00192-2","article-title":"From local to global consistency in temporal constraint networks","volume":"Vol. 173","author":"Koubarakis","year":"1997","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0004-3702(00)00055-2_ID046","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0304-3975(96)00124-7","article-title":"The complexity of query evaluation in indefinite temporal constraint databases","volume":"Vol. 171","author":"Koubarakis","year":"1997","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0004-3702(00)00055-2_ID047","series-title":"Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning","author":"Koubarakis","year":"1999"},{"key":"10.1016\/S0004-3702(00)00055-2_ID048","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(84)90009-2","article-title":"Foundations of a functional approach to knowledge representation","volume":"Vol. 23","author":"Levesque","year":"1984","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID049","doi-asserted-by":"crossref","DOI":"10.1006\/jvlc.1997.9999","article-title":"Reasoning about cardinal directions","volume":"Vol. 9","author":"Ligozat","year":"1998","journal-title":"J. Visual Languages and Computing"},{"issue":"3","key":"10.1016\/S0004-3702(00)00055-2_ID050","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/320083.320088","article-title":"On semantic issues connected with incomplete information databases","volume":"Vol. 4","author":"Lipski","year":"1979","journal-title":"ACM Trans. Database Systems"},{"issue":"1","key":"10.1016\/S0004-3702(00)00055-2_ID051","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0747-7171(92)90002-L","article-title":"A canonical form for generalized linear constraints","volume":"Vol. 13","author":"Lassez","year":"1992","journal-title":"J. Symbolic Comput."},{"issue":"4","key":"10.1016\/S0004-3702(00)00055-2_ID052","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1145\/102675.102676","article-title":"Telos: A language for representing knowledge about information systems","volume":"Vol. 8","author":"Mylopoulos","year":"1990","journal-title":"ACM Trans. Inform. Systems"},{"issue":"1","key":"10.1016\/S0004-3702(00)00055-2_ID053","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","article-title":"Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra","volume":"Vol. 42","author":"Nebel","year":"1995","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(00)00055-2_ID054","series-title":"Proc. VLDB-93","first-page":"146","article-title":"Integrity constraint and rule maintenance in temporal deductive knowledge bases","author":"Plexousakis","year":"1993"},{"key":"10.1016\/S0004-3702(00)00055-2_ID055","series-title":"Proc. 1995 ACM SIGMOD International Conference on Management of Data","first-page":"92","article-title":"Topological relations in the world of minimum bounding rectangles: A study with R-trees","author":"Papadias","year":"1995"},{"key":"10.1016\/S0004-3702(00)00055-2_ID056","series-title":"On Conceptual Modelling: Perspectives from Artificial Intelligence, Databases and Programming Languages","first-page":"191","article-title":"Towards a logical reconstruction of relational database theory","author":"Reiter","year":"1984"},{"key":"10.1016\/S0004-3702(00)00055-2_ID057","series-title":"Proc. 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, Asilomar, CA","first-page":"97","article-title":"On integrity constraints","author":"Reiter","year":"1988"},{"key":"10.1016\/S0004-3702(00)00055-2_ID058","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0004-3702(99)00002-8","article-title":"On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus","volume":"Vol. 108","author":"Renz","year":"1999","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID059","series-title":"Proc. KR-92","first-page":"36","article-title":"Managing disjunction for practical temporal reasoning","author":"Schrag","year":"1992"},{"key":"10.1016\/S0004-3702(00)00055-2_ID060","series-title":"Theory of Integer and Linear Programming","year":"1986"},{"issue":"4","key":"10.1016\/S0004-3702(00)00055-2_ID061","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1145\/322276.322288","article-title":"Deciding linear inequalities by computing loop residues","volume":"Vol. 28","author":"Shostak","year":"1981","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(00)00055-2_ID062","series-title":"The TSQL2 Temporal Query Language","year":"1995"},{"key":"10.1016\/S0004-3702(00)00055-2_ID063","series-title":"Proc. ICLP-97","first-page":"301","article-title":"Constraint search trees","author":"Stuckey","year":"1997"},{"key":"10.1016\/S0004-3702(00)00055-2_ID064","series-title":"Proc. ACM SIGACT\/SIGMOD Symposium on Principles of Database Systems","first-page":"137","article-title":"The complexity of relational query languages","author":"Vardi","year":"1982"},{"key":"10.1016\/S0004-3702(00)00055-2_ID065","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0933-3657(91)90004-U","article-title":"Temporal query processing with indefinite information","volume":"Vol. 3","author":"van Beek","year":"1991","journal-title":"Artificial Intelligence in Medicine"},{"key":"10.1016\/S0004-3702(00)00055-2_ID066","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0004-3702(92)90011-L","article-title":"Reasoning about qualitative temporal information","volume":"Vol. 58","author":"van Beek","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID067","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1111\/j.1467-8640.1990.tb00130.x","article-title":"Exact and approximate reasoning about temporal relations","volume":"Vol. 6","author":"van Beek","year":"1990","journal-title":"Computational Intelligence"},{"key":"10.1016\/S0004-3702(00)00055-2_ID068","series-title":"Proc. 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","first-page":"331","article-title":"The complexity of querying indefinite data about linearly ordered domains (Preliminary version)","author":"van der Meyden","year":"1992"},{"key":"10.1016\/S0004-3702(00)00055-2_ID069","series-title":"Proc. AAAI-86, Philadelphia, PA","first-page":"377","article-title":"Constraint propagation algorithms for temporal reasoning","author":"Vilain","year":"1986"},{"key":"10.1016\/S0004-3702(00)00055-2_ID070","series-title":"Readings in Qualitative Reasoning about Physical Systems","first-page":"373","article-title":"Constraint propagation algorithms for temporal reasoning: A revised report","author":"Vilain","year":"1989"},{"key":"10.1016\/S0004-3702(00)00055-2_ID071","series-title":"Proc. ACM Symposium on the Theory of Computing","first-page":"223","article-title":"Expressing combinatorial optimization problems by linear programs","author":"Yannakakis","year":"1988"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370200000552?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370200000552?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T12:28:17Z","timestamp":1556195297000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370200000552"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,10]]},"references-count":66,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2000,10]]}},"alternative-id":["S0004370200000552"],"URL":"https:\/\/doi.org\/10.1016\/s0004-3702(00)00055-2","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[2000,10]]}}}