{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:03Z","timestamp":1781077863520,"version":"3.54.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,5,1]],"date-time":"2010-05-01T00:00:00Z","timestamp":1272672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001823","name":"Ministry of Education, Youth and Sports","doi-asserted-by":"publisher","award":["1M0021620808"],"award-info":[{"award-number":["1M0021620808"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2010,5]]},"abstract":"<jats:p>We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of B\u00fcrkert and Nebel and the class of AND\/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) the constraint satisfaction problem of this language cannot be solved by Datalog or by establishing local consistency.<\/jats:p>","DOI":"10.1145\/1740582.1740583","type":"journal-article","created":{"date-parts":[[2010,5,18]],"date-time":"2010-05-18T13:46:22Z","timestamp":1274190382000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["A fast algorithm and datalog inexpressibility for temporal reasoning"],"prefix":"10.1145","volume":"11","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Laboratoire d'Informatique (LIX, CNRS UMR 6171), \u00c9cole Polytechnique, Paris-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,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/182.358434"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_53"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_53"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374382"},{"key":"e_1_2_1_5_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 (Montreal, 2003), NATO Science Series II: Mathematics, Physics","volume":"207","author":"Bulatov A.","year":"2005","unstructured":"Bulatov , A. , Jeavons , P. , and Krokhin , A. 2005 . The complexity of constraint satisfaction: An algebraic approach (a survey paper). In Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics , Chemistry , vol. 207. 181 -- 213 . Bulatov, A., Jeavons, P., and Krokhin, A. 2005. The complexity of constraint satisfaction: An algebraic approach (a survey paper). In Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics, Chemistry, vol. 207. 181--213.","journal-title":"Chemistry"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_7_1","unstructured":"Creignou N. Hermann M. Krokhin A. and Salzer G. 2005. Complexity of clausal constraints over chains. Res. rep. Ecole Polytechnique Paris-Palaiseau France.  Creignou N. Hermann M. Krokhin A. and Salzer G. 2005. Complexity of clausal constraints over chains. Res. rep. Ecole Polytechnique Paris-Palaiseau France."},{"key":"e_1_2_1_8_1","volume-title":"Constraint Processing. Morgan Kaufmann","author":"Dechter R.","unstructured":"Dechter , R. 2003. Constraint Processing. Morgan Kaufmann , San Francisco, CA . Dechter, R. 2003. Constraint Processing. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_9_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"Diestel , R. 2005. Graph Theory , 3 rd Ed. Springer--Verlag , New York, NY . Diestel, R. 2005. Graph Theory, 3rd Ed. Springer--Verlag, New York, NY.","edition":"3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00021-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-004-5899-8"},{"key":"e_1_2_1_12_1","unstructured":"Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd ed. Springer Berlin Germany.  Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd ed. Springer Berlin Germany."},{"key":"e_1_2_1_13_1","unstructured":"Fisher M. Gabbay D. and Vila L. 2005. Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier Amsterdam The Netherlands.   Fisher M. Gabbay D. and Vila L. 2005. Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier Amsterdam The Netherlands."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_15_1","unstructured":"Garey M. and Johnson D. 1978. A Guide to NP-Completeness. CSLI Press Stanford CA.  Garey M. and Johnson D. 1978. A Guide to NP-Completeness. CSLI Press Stanford CA."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-34735-6_10"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/174147.169675"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford University Press Oxford U.K.  Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford University Press Oxford U.K.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_19_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_20_1","doi-asserted-by":"crossref","unstructured":"Janson S. Luczak T. and Rucinski A. 2000. Random Graphs. John Wiley and Sons New York NY.  Janson S. Luczak T. and Rucinski A. 2000. Random Graphs. John Wiley and Sons New York NY.","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876639"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00177-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275511"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/176584.176585"},{"key":"e_1_2_1_25_1","volume-title":"Model Theory: An Introduction","author":"Marker D.","year":"2002","unstructured":"Marker , D. 2002 . Model Theory: An Introduction . Springer , Berlin, Germany . Marker, D. 2002. Model Theory: An Introduction. Springer, Berlin, Germany."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970037727X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200848"},{"key":"e_1_2_1_28_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 P.Q. 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 P.Q. Canada."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90011-L"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1455"},{"key":"e_1_2_1_31_1","volume-title":"Reading in Qualitative Reasoning about Physical Systems, Morgan Kaufmann","author":"Vilain M.","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, Morgan Kaufmann , San Francisco, CA , 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, Morgan Kaufmann, San Francisco, CA, 373--381."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1740582.1740583","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1740582.1740583","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:55Z","timestamp":1750250455000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1740582.1740583"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["10.1145\/1740582.1740583"],"URL":"https:\/\/doi.org\/10.1145\/1740582.1740583","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5]]},"assertion":[{"value":"2008-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-05-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}