{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:05Z","timestamp":1781077865714,"version":"3.54.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>\n            A\n            <jats:italic>temporal constraint language<\/jats:italic>\n            is a set of relations that has a first-order definition in(Q;&lt;), the dense linear order of the rational numbers. We present a complete complexity classification of the constraint satisfaction problem (CSP) for temporal constraint languages: if the constraint language is contained in one out of nine temporal constraint languages, then the CSP can be solved in polynomial time; otherwise, the CSP is NP-complete. Our proof combines model-theoretic concepts with techniques from universal algebra, and also applies the so-called product Ramsey theorem, which we believe will useful in similar contexts of constraint satisfaction complexity classification.\n          <\/jats:p>\n          <jats:p>An extended abstract of this article appeared in the proceedings of STOC'08.<\/jats:p>","DOI":"10.1145\/1667053.1667058","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T13:16:40Z","timestamp":1282655800000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":81,"title":["The complexity of temporal constraint satisfaction problems"],"prefix":"10.1145","volume":"57","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique, Palaiseau, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"K\u00e1ra","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,2,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(1:2)2007"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.050"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Bodirsky M. and Dalmau V. 2008. Datalog and constraint satisfaction with infinite templates. arXiv:0809.2386 {cs.LO}.  Bodirsky M. and Dalmau V. 2008. Datalog and constraint satisfaction with infinite templates. arXiv:0809.2386 {cs.LO}.","DOI":"10.1007\/978-3-540-92800-3_8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1740582.1740583"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"e_1_2_1_7_1","unstructured":"Bodirsky M. and Pinsker M. 2009. All reducts of the random graph are model-complete. Preprint arXiv:0810.2270.  Bodirsky M. and Pinsker M. 2009. All reducts of the random graph are model-complete. Preprint arXiv:0810.2270."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(03)00075-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789067"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021881"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_13_1","first-page":"181","article-title":"The complexity of constraint satisfaction: An algebraic approach (a survey paper). In Structural Theory of Automata, Semigroups and Universal Algebra. NATO Science Series II: Mathematics, Physics","volume":"207","author":"Bulatov A.","year":"2005","unstructured":"Bulatov , A. , Jeavons , P. , and Krokhin , A. 2005 a. The complexity of constraint satisfaction: An algebraic approach (a survey paper). In Structural Theory of Automata, Semigroups and Universal Algebra. NATO Science Series II: Mathematics, Physics , Chemistry 207 , 181 -- 213 . Bulatov, A., Jeavons, P., and Krokhin, A. 2005a. The complexity of constraint satisfaction: An algebraic approach (a survey paper). In Structural Theory of Automata, Semigroups and Universal Algebra. NATO Science Series II: Mathematics, Physics, Chemistry 207, 181--213.","journal-title":"Chemistry"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01214702"},{"key":"e_1_2_1_16_1","volume-title":"Oligomorphic Permutation Groups","author":"Cameron P. J.","unstructured":"Cameron , P. J. 1990. Oligomorphic Permutation Groups . Cambridge University Press, Cambridge , UK. Cameron, P. J. 1990. Oligomorphic Permutation Groups. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01446598"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/355483.355485"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Creignou N. Khanna S. and Sudan M. 2001. Complexity classifications of Boolean constraint satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications 7.   Creignou N. Khanna S. and Sudan M. 2001. Complexity classifications of Boolean constraint satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications 7.","DOI":"10.1137\/1.9780898718546"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of CP'99","author":"Dalmau V.","unstructured":"Dalmau , V. , and Pearson , J . 1999. Closure functions and width 1 problems . In Proceedings of CP'99 . 159--173. Dalmau, V., and Pearson, J. 1999. Closure functions and width 1 problems. In Proceedings of CP'99. 159--173."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00021-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/8.6.855"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_24_1","unstructured":"Garey M. and Johnson D. 1978. A Guide to NP-Completeness. CSLI Press.  Garey M. and Johnson D. 1978. A Guide to NP-Completeness. CSLI Press."},{"key":"e_1_2_1_25_1","first-page":"95","article-title":"Closed systems of functions and predicates. Paci","volume":"27","author":"Geiger D.","year":"1968","unstructured":"Geiger , D. 1968 . Closed systems of functions and predicates. Paci . J. Math. 27 , 95 -- 100 . Geiger, D. 1968. Closed systems of functions and predicates. Paci. J. Math. 27, 95--100.","journal-title":"J. Math."},{"key":"e_1_2_1_26_1","unstructured":"Graham R. L. Rothschild B. L. and Spencer J. H. 1990. Ramsey Theory 2nd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley New York.   Graham R. L. Rothschild B. L. and Spencer J. H. 1990. Ramsey Theory 2nd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley New York."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03351-3_12"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 4th IFIP International Conference on Theoretical Computer Science (TCS'06)","author":"Guttmann W.","unstructured":"Guttmann , W. , and Maucher , M . 2006. Variations on an ordering theme with constraints . In Proceedings of the 4th IFIP International Conference on Theoretical Computer Science (TCS'06) . IFIP International Federation for Information Processing 209. 77--90. Guttmann, W., and Maucher, M. 2006. Variations on an ordering theme with constraints. In Proceedings of the 4th IFIP International Conference on Theoretical Computer Science (TCS'06). IFIP International Federation for Information Processing 209. 77--90."},{"key":"e_1_2_1_29_1","volume-title":"A Shorter Model Theory","author":"Hodges W.","unstructured":"Hodges , W. 1997. A Shorter Model Theory . Cambridge University Press , Cambridge, U.K. Hodges, W. 1997. A Shorter Model Theory. Cambridge University Press, Cambridge, U.K."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.50"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00107-7"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622767.1622774"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1230396752"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876639"},{"key":"e_1_2_1_36_1","volume-title":"Model Theory: An Introduction","author":"Marker D.","year":"2002","unstructured":"Marker , D. 2002 . Model Theory: An Introduction . Springer , New York . Marker, D. 2002. Model Theory: An Introduction. Springer, New York."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970037727X"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200848"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_40_1","unstructured":"Szendrei A. 1986. Clones in universal Algebra. S\u00e9minaire de Math\u00e9matiques Sup\u00e9rieures. Les Presses de L'Universit\u00e9 de Montr\u00e9al Montreal Ont. Canada.  Szendrei A. 1986. Clones in universal Algebra. S\u00e9minaire de Math\u00e9matiques Sup\u00e9rieures. Les Presses de L'Universit\u00e9 de Montr\u00e9al Montreal Ont. Canada."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90011-L"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Vilain M. Kautz H. and van Beek P. 1989. Constraint propagation algorithms for temporal reasoning: A revised report. In Reading in Qualitative Reasoning about Physical Systems 373--381.   Vilain M. Kautz H. and van Beek P. 1989. Constraint propagation algorithms for temporal reasoning: A revised report. In Reading in Qualitative Reasoning about Physical Systems 373--381.","DOI":"10.1016\/B978-1-4832-1447-4.50034-1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1667053.1667058","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1667053.1667058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:30Z","timestamp":1750250490000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1667053.1667058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1145\/1667053.1667058"],"URL":"https:\/\/doi.org\/10.1145\/1667053.1667058","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]},"assertion":[{"value":"2008-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}