{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:58:06Z","timestamp":1787497086351,"version":"build-2736575974"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T00:00:00Z","timestamp":1671408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["681988"],"award-info":[{"award-number":["681988"]}]},{"name":"DFG Graduiertenkolleg","award":["1763"],"award-info":[{"award-number":["1763"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,2,28]]},"abstract":"<jats:p>\n                    Finite-domain constraint satisfaction problems are either solvable by Datalog or not even expressible in fixed-point logic with counting. The border between the two regimes can be described by a universal-algebraic minor condition. For infinite-domain constraint satisfaction problems (CSPs), the situation is more complicated even if the template structure of the CSP is model-theoretically tame. We prove that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (\u211a;&lt;); such CSPs are called\n                    <jats:italic>temporal CSPs<\/jats:italic>\n                    and are of fundamental importance in infinite-domain constraint satisfaction. Our main result is a complete classification of temporal CSPs that can be expressed in one of the following logical formalisms: Datalog, fixed-point logic (with or without counting), or fixed-point logic with the mod-2 rank operator. The classification shows that many of the equivalent conditions in the finite fail to capture expressibility in Datalog or fixed-point logic already for temporal CSPs.\n                  <\/jats:p>","DOI":"10.1145\/3566051","type":"journal-article","created":{"date-parts":[[2022,10,17]],"date-time":"2022-10-17T09:07:21Z","timestamp":1665997641000},"page":"1-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Descriptive Complexity of Temporal Constraint Satisfaction Problems"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8228-3611","authenticated-orcid":false,"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"TU Dresden, Dresden, Deutschland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7961-9492","authenticated-orcid":false,"given":"Jakub","family":"Rydval","sequence":"additional","affiliation":[{"name":"TU Wien, Wien, \u00d6sterreich"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,12,19]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.004"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.049"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exz022"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3457606"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061319500107"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_3_2_8_2","series-title":"Dagstuhl Follow-Ups","first-page":"1","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability","author":"Barto L.","year":"2017","unstructured":"L. Barto, A. Krokhin, and R. Willard. 2017. Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability, A. Krokhin and S. \u017divn\u00fd (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 1\u201344."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1190150152"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781107337534"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196714500507"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.05.012"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1740582.1740583"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934515"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/3470152.3470212"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/558\/11058"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05975-8"},{"issue":"2","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"36","DOI":"10.55016\/ojs\/cdm.v16i2.71724","article-title":"Canonical functions: A proof via topological dynamics","volume":"16","author":"Bodirsky M.","year":"2021","unstructured":"M. Bodirsky and M. Pinsker. 2021. Canonical functions: A proof via topological dynamics. Contributions to Discrete Mathematics 16, 2 (2021), 36\u201345.","journal-title":"Contributions to Discrete Mathematics"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_24_2","first-page":"77","volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC\u201977)","author":"Chandra A. K.","year":"1977","unstructured":"A. K. Chandra and P. M. Merlin. 1977. Optimal implementation of conjunctive queries in relational databases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC\u201977). ACM, New York, NY, 77\u201390."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1998.0641"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2728816.2728820"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.24"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","unstructured":"A. Dawar and S. Kreutzer. 2008. On Datalog vs. LFP. In Automata Languages and Programming . Lecture Notes in Computer Science Vol. 5126. Springer 160\u2013171.","DOI":"10.1007\/978-3-540-70583-3_14"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330043"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2003.1210071"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1383471"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03351-3_12"},{"issue":"1","key":"e_1_3_2_34_2","first-page":"Article 4, 53 p","article-title":"A finite-model-theoretic view on propositional proof complexity","volume":"15","author":"Gr\u00e4del E.","year":"2019","unstructured":"E. Gr\u00e4del, M. Grohe, B. Pago, and W. Pakusa. 2019. A finite-model-theoretic view on propositional proof complexity. Logical Methods in Computer Science 15, 1 (2019), Article 4, 53 pages.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68804-8_3"},{"key":"e_1_3_2_36_2","first-page":"231","volume-title":"Selected Papers from the 6th International Workshop on Computer Science Logic (CSL\u201992)","author":"Gr\u00e4del E.","year":"1992","unstructured":"E. Gr\u00e4del and M. Otto. 1992. Inductive definability with counting on finite structures. In Selected Papers from the 6th International Workshop on Computer Science Logic (CSL\u201992). Springer-Verlag, Berlin, Germany, 231\u2013247."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2018.33"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.11"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.2307\/2275675"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/090756144"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/262326"},{"key":"e_1_3_2_42_2","first-page":"229","article-title":"Homomorphism and embedding universal structures for restricted classes.","volume":"27","author":"Hubi\u010dka J.","year":"2016","unstructured":"J. Hubi\u010dka and J. Ne\u0161et\u0159il. 2016. Homomorphism and embedding universal structures for restricted classes.Journal of Multiple-Valued Logic & Soft Computing 27 (2016), 229\u2013253.","journal-title":"Journal of Multiple-Valued Logic & Soft Computing"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-015-0327-2"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.02.001"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1142\/S021819670900524X"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-007-2012-6"},{"key":"e_1_3_2_48_2","volume-title":"Elements of Finite Model Theory","author":"Libkin L.","year":"2013","unstructured":"L. Libkin. 2013. Elements of Finite Model Theory. Springer, Berlin, Germany."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470598"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2122-9"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200848"},{"key":"e_1_3_2_53_2","unstructured":"M. Ol\u0161\u00e1k. 2019. Generalizing CSP-Related Results to Infinite Algebras . Ph.D. Thesis. Univerzita Karlova Matematicko-fyzik\u00e1ln\u00ed fakulta."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2021.14"},{"key":"e_1_3_2_55_2","volume-title":"Bounded Variable Logics and Counting: A Study in Finite Model Theory","author":"Otto M.","year":"2000","unstructured":"M. Otto. 2000. Bounded Variable Logics and Counting: A Study in Finite Model Theory. Springer, Berlin, Germany."},{"key":"e_1_3_2_56_2","unstructured":"W. Pakusa. 2015. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time . Ph.D. Dissertation. RWTH Aachen."},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379763"},{"key":"e_1_3_2_58_2","unstructured":"P. Wang. 2018. Descriptive Complexity of Constraint Problems . Ph.D. Dissertation. University of Cambridge."},{"issue":"4","key":"e_1_3_2_59_2","first-page":"455","article-title":"Strong subalgebras and the constraint satisfaction problem.","volume":"36","author":"Zhuk D.","year":"2021","unstructured":"D. Zhuk. 2021. Strong subalgebras and the constraint satisfaction problem.Journal of Multiple-Valued Logic & Soft Computing 36, 4 (2021), 455\u2013504.","journal-title":"Journal of Multiple-Valued Logic & Soft Computing"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3566051","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3566051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T14:08:33Z","timestamp":1750169313000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3566051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,19]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1145\/3566051"],"URL":"https:\/\/doi.org\/10.1145\/3566051","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,19]]},"assertion":[{"value":"2021-06-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}