{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T23:24:47Z","timestamp":1768433087266,"version":"3.49.0"},"reference-count":36,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,9,1]],"date-time":"2001-09-01T00:00:00Z","timestamp":999302400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4337,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,9]]},"DOI":"10.1016\/s0304-3975(00)00177-8","type":"journal-article","created":{"date-parts":[[2002,10,31]],"date-time":"2002-10-31T21:53:12Z","timestamp":1036101192000},"page":"311-339","source":"Crossref","is-referenced-by-count":35,"title":["Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning"],"prefix":"10.1016","volume":"266","author":[{"given":"Manolis","family":"Koubarakis","sequence":"first","affiliation":[]}],"member":"78","reference":[{"issue":"11","key":"10.1016\/S0304-3975(00)00177-8_BIB1","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","article-title":"Maintaining knowledge about temporal intervals","volume":"26","author":"Allen","year":"1983","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB2","unstructured":"H. Beringer, B. de Backer, Satisfiability of Boolean formulas over linear constraints, in: Proc. IJCAI-93, Morgan Kaufmann, Los Altos, CA, 1993, pp. 296\u2013301."},{"issue":"1","key":"10.1016\/S0304-3975(00)00177-8_BIB3","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0004-3702(89)90080-5","article-title":"An optimal k-consistency algorithm","volume":"41","author":"Cooper","year":"1990","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB4","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0004-3702(92)90043-W","article-title":"From local to global consistency","volume":"55","author":"Dechter","year":"1992","journal-title":"Artificial Intelligence"},{"issue":"1\u20133","key":"10.1016\/S0304-3975(00)00177-8_BIB5","first-page":"61","article-title":"Temporal constraint networks","volume":"49","author":"Dechter","year":"1991","journal-title":"Artificial Intelligence (Special Volume on Knowledge Representation)"},{"issue":"11","key":"10.1016\/S0304-3975(00)00177-8_BIB6","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1145\/359642.359654","article-title":"Synthesizing constraint expressions","volume":"21","author":"Freuder","year":"1978","journal-title":"Comm. ACM"},{"issue":"1","key":"10.1016\/S0304-3975(00)00177-8_BIB7","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","article-title":"A sufficient condition for backtrack-free search","volume":"29","author":"Freuder","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB8","series-title":"Convex Polytopes","author":"Grunbaum","year":"1967"},{"issue":"5","key":"10.1016\/S0304-3975(00)00177-8_BIB9","first-page":"473","article-title":"Variable elimination for disequations in generalized linear constraint systems","volume":"36","author":"Imbert","year":"1993","journal-title":"Comput. J. (Special Issue on Variable Elimination)"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB10","unstructured":"J.-L. Imbert, Variable elimination for generalized linear constraints: particular problems involving disequalities, Proc. 10th Internat. Conf. on Logic Programming, MIT Press, Cambridge, MA, 1993, pp. 499\u2013516."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB11","unstructured":"J.-L. Imbert, Redundancy, variable elimination and linear disequations, Proc. Internat. Symp. on Logic Programming, 1994 pp. 139\u2013153."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB12","series-title":"Constraint Logic Programming: Selected Research, Logic Programming Series","first-page":"49","article-title":"On the handling of disequations in CLP over linear rational arithmetic","author":"Imbert","year":"1993"},{"issue":"20","key":"10.1016\/S0304-3975(00)00177-8_BIB13","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/0743-1066(94)90033-7","article-title":"Constraint logic programming","volume":"19","author":"Jaffar","year":"1994","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB14","unstructured":"P. Jonsson, C. B\u00e4ckstr\u00f6m, A linear programming approach to temporal reasoning, Proc. AAAI-96, AAAI Press\/MIT Press, Cambridge, MA, 1996, pp. 1235\u20131240."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB15","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":"102","author":"Jonsson","year":"1998","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB16","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\/S0304-3975(00)00177-8_BIB17","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"20","author":"Khachiyan","year":"1979","journal-title":"Sov. Math. Dokl."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB18","unstructured":"M. Koubarakis, Dense time and temporal constraints with \u2260, in: Principles of Knowledge Representation and Reasoning: Proc. 3rd Internat. Conf., KR\u201992, Morgan Kaufmann, San Mateo, CA, October 1992, pp. 24\u201335."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB19","doi-asserted-by":"crossref","unstructured":"M. Koubarakis, Complexity results for first-order theories of temporal constraints, in: Principles of Knowledge Representation and Reasoning: Proc. 4th Internat. Conf. (KR\u201994), Morgan Kaufmann, San Francisco, CA, May 1994, pp. 379\u2013390.","DOI":"10.1016\/B978-1-4832-1452-8.50131-7"},{"issue":"2","key":"10.1016\/S0304-3975(00)00177-8_BIB20","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0306-4379(94)90008-6","article-title":"Database models for infinite and indefinite temporal information","volume":"19","author":"Koubarakis","year":"1994","journal-title":"Inform. Systems"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB21","first-page":"266","article-title":"Foundations of indefinite constraint databases","volume":"vol. 874","author":"Koubarakis","year":"1994"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB22","doi-asserted-by":"crossref","unstructured":"M. Koubarakis, From local to global consistency in temporal constraint networks in: Proc. 1st Internat. Conf. on Principles and Practice of Constraint Programming (CP\u201995), Lecture Notes in Computer Science, vol. 976, Cassis, France, Springer, Berlin, September 1995, pp. 53\u201369.","DOI":"10.1007\/3-540-60299-2_4"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB23","doi-asserted-by":"crossref","unstructured":"M. Koubarakis, From local to global consistency in temporal constraint networks, Theoret. Comput. Sci. 173 (1997) 89\u2013112. Invited submission to the special issue dedicated to the 1st Internat. Conf. on Principles and Practice of Constraint Programming (CP95), Editors: U. Montanari and F. Rossi.","DOI":"10.1016\/S0304-3975(96)00192-2"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB24","doi-asserted-by":"crossref","unstructured":"M. Koubarakis, The complexity of query evaluation in indefinite temporal constraint databases, Theoret. Comput. Sci. 171 (1997) 25\u201360. Special Issue on Uncertainty in Databases and Deductive Systems, Editor: L.V.S. Lakshmanan.","DOI":"10.1016\/S0304-3975(96)00124-7"},{"issue":"3","key":"10.1016\/S0304-3975(00)00177-8_BIB25","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","article-title":"On binary constraint problems","volume":"41","author":"Ladkin","year":"1994","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB26","unstructured":"J.-L. Lassez, K. McAloon, A canonical form for generalized linear constraints, Technical Report RC15004 (#67009), IBM Research Division, T.J. Watson Research Center, 1989."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB27","doi-asserted-by":"crossref","unstructured":"J.-L. Lassez, K. McAloon, A canonical form for generalized linear costraints, in: TAPSOFT \u201989, Advanced Seminar on Foundations of Innovative Software Development, Lecture Notes in Computer Science, vol. 351, Springer, Berlin, 1989, pp. 19\u201327.","DOI":"10.1007\/3-540-50939-9_122"},{"issue":"1","key":"10.1016\/S0304-3975(00)00177-8_BIB28","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":"13","author":"Lassez","year":"1992","journal-title":"J. Symbolic Comput."},{"issue":"1","key":"10.1016\/S0304-3975(00)00177-8_BIB29","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":"42","author":"Nebel","year":"1995","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB30","unstructured":"B. Nebel, H.-J. B\u00fcrckert, C programs used for the analysis of the ORD-Horn class, available electronically from ftp:\/\/ftp. informatik.uni-freiburg.de\/\u00a0\u0303nebel\/journals.html."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB31","series-title":"Theory of Integer and Linear Programming","year":"1986"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB32","unstructured":"S. Skiadopoulos, Tractable query answering in indefinite linear constraint databases, Master's Thesis, Department of Computation, UMIST, 1998."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB33","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0020-0190(85)90076-6","article-title":"Real addition and the polynomial time hierarchy","volume":"20","author":"Sontag","year":"1985","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(00)00177-8_BIB34","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0004-3702(92)90011-L","article-title":"Reasoning about qualitative temporal information","volume":"58","author":"van Beek","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB35","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":"6","author":"van Beek","year":"1990","journal-title":"Comput. Intelligence"},{"key":"10.1016\/S0304-3975(00)00177-8_BIB36","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"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500001778?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500001778?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T10:29:50Z","timestamp":1578652190000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500001778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,9]]},"references-count":36,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,9]]}},"alternative-id":["S0304397500001778"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00177-8","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,9]]}}}