{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:19Z","timestamp":1787340319070,"version":"build-2736575974"},"reference-count":99,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["467967530"],"award-info":[{"award-number":["467967530"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101071674"],"award-info":[{"award-number":["101071674"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001862","name":"Svenska Forskningsr\u00e5det Formas","doi-asserted-by":"publisher","award":["2017-04112"],"award-info":[{"award-number":["2017-04112"]}],"id":[{"id":"10.13039\/501100001862","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001862","name":"Svenska Forskningsr\u00e5det Formas","doi-asserted-by":"publisher","award":["2021-04371"],"award-info":[{"award-number":["2021-04371"]}],"id":[{"id":"10.13039\/501100001862","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X03190X\/1"],"award-info":[{"award-number":["EP\/X03190X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study the complexity of infinite-domain constraint satisfaction problems (CSPs): our basic setting is that a complexity classification for the CSPs of first-order expansions of a structure [Formula: see text] can be transferred to a classification of the CSPs of first-order expansions of another structure [Formula: see text]. We exploit a product of structures (the algebraic product) that corresponds to the product of the respective polymorphism clones and present a complete complexity classification of the CSPs for first-order expansions of the [Formula: see text]-fold algebraic power of [Formula: see text]. This is proved by various algebraic and logical methods in combination with knowledge of the polymorphisms of the tractable first-order expansions of [Formula: see text] and explicit descriptions of the expressible relations in terms of syntactically restricted first-order formulas. By combining our classification result with general classification transfer techniques, we obtain surprisingly strong new classification results for highly relevant formalisms such as Allen\u2019s Interval Algebra, the [Formula: see text]-dimensional Block Algebra, and the Cardinal Direction Calculus, even if higher-arity relations are allowed. Our results confirm the infinite-domain tractability conjecture for classes of structures that have been difficult to analyze with older methods. For the special case of structures with binary signatures, the results can be substantially strengthened and tightly connected to Ord-Horn formulas; this solves several longstanding open problems from the artificial intelligence (AI) literature.<\/jats:p>","DOI":"10.1137\/22m1534304","type":"journal-article","created":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T04:20:26Z","timestamp":1726114826000},"page":"1293-1353","source":"Crossref","is-referenced-by-count":2,"title":["Complexity Classification Transfer for CSPs via Algebraic Products"],"prefix":"10.1137","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8228-3611","authenticated-orcid":true,"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Institute of Algebra, TU Dresden, Dresden, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, Link\u00f6ping University, Link\u00f6ping, Sweden."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, Durham, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antoine","family":"Mottet","sequence":"additional","affiliation":[{"name":"Research Group for Theoretical Computer Science, Hamburg University of Technology, Hamburg, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8111-0671","authenticated-orcid":true,"given":"\u017daneta","family":"Semani\u0161inov\u00e1","sequence":"additional","affiliation":[{"name":"Institute of Algebra, TU Dresden, Dresden, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,9,12]]},"reference":[{"key":"ref1","first-page":"623","volume":"131","author":"Adeleke S. A.","year":"1998","journal-title":"Mem. Amer. Math. Soc."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90037-0"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/182.358434"},{"key":"ref4","unstructured":"J. F. Allen and P. J. Hayes, A common-sense theory of time, in Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI-1985), 1985, pp. 528\u2013531."},{"key":"ref5","unstructured":"J. F. Allen and J. A. G. M. Koomen, Planning using a temporal world model, in Proceedings of the 8th International Joint Conference on Artificial Intelligence (IJCAI-1983), 1983, pp. 741\u2013747."},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/65979.65982"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"F. Baader and J. Rydval, Description logics with concrete domains and general concept inclusions revisited, in Proceedings of the 10th International Joint Conference on Automated Reasoning (IJCAR-2020), 2020, pp. 413\u2013431.","DOI":"10.1007\/978-3-030-51074-9_24"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020079114666"},{"key":"ref9","unstructured":"P. Balbiani, J. Condotta, and L. F. del Cerro, A new tractable subclass of the rectangle algebra, in Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-1999), 1999, pp. 442\u2013447."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/12.5.885"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/LICS56636.2023.10175732"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061319500107"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"L. Barto and M. Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, in Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science (LICS-2016), 2016, pp. 615\u2013622.","DOI":"10.1145\/2933575.2934544"},{"key":"ref15","unstructured":"A. Bertagnon, M. Gavanelli, A. Passantino, G. Sciavicco, and S. Trevisani, The Horn fragment of branching algebra, in Proceedings of the 27th International Symposium on Temporal Representation and Reasoning (TIME-2020), 2020, pp. 5:1\u20135:16."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104809"},{"key":"ref17","unstructured":"A. Bertagnon, M. Gavanelli, G. Sciavicco, and S. Trevisani, On (maximal, tractable) fragments of the branching algebra, in Proceedings of the 35th Italian Conference on Computational Logic (CILC-2020), 2020, pp. 113\u2013126."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/2661643"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1017\/9781107337534"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and B. Bodor, Canonical polymorphisms of Ramsey structures and the unique interpolation property, in Proceedings of the 36th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS-2021), 2021, pp. 1\u201313.","DOI":"10.1109\/LICS52264.2021.9470683"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1286198146"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196714500507"},{"key":"ref23","first-page":"21","volume":"16","author":"Bodirsky M.","year":"2020","journal-title":"Log. Methods Comput. Sci."},{"key":"ref24","first-page":"11","volume":"18","author":"Bodirsky M.","year":"2022","journal-title":"Log. Methods Comput. Sci."},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and M. Grohe, Non-dichotomies in constraint satisfaction complexity, in Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP-2008), 2008, pp. 184\u2013196.","DOI":"10.1007\/978-3-540-70583-3_16"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5260"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"M. Bodirsky, P. Jonsson, B. Martin, and A. Mottet, Classification transfer for qualitative reasoning problems, in Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-2018), 2018, pp. 1256\u20131262.","DOI":"10.24963\/ijcai.2018\/175"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1145\/3105907"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and J. K\u00e1ra, The complexity of temporal constraint satisfaction problems, in Proceedings of the 40th Annual Symposium on Theory of Computing (STOC), C. Dwork, ed. ACM, 2008, pp. 29\u201338.","DOI":"10.1145\/1374376.1374382"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/1740582.1740583"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and S. Kn\u00e4uer, Network satisfaction for symmetric relation algebras with a flexible atom, in Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI-2021), 2021, pp. 6218\u20136226.","DOI":"10.1609\/aaai.v35i7.16773"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/19M128466X"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082974"},{"key":"ref35","first-page":"13","volume":"14","author":"Bodirsky M.","year":"2018","journal-title":"Log. Methods Comput. Sci."},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and J. Ne\u0161et\u0159il, Constraint satisfaction with countable homogeneous templates, in Proceedings of Computer Science Logic (CSL), Vienna, 2003, pp. 44\u201357.","DOI":"10.1007\/978-3-540-45220-1_5"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"M. Bodirsky, W. Pakusa, and J. Rydval, Temporal constraint satisfaction problems in fixed-point logic, in Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS-2020), 2020, pp. 237\u2013251.","DOI":"10.1145\/3373718.3394750"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/3566051"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1145\/2764899"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05975-8"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.55016\/ojs\/cdm.v16i2.71724"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2019.23"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.2178\/jsl.7804020"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov, A dichotomy theorem for nonuniform CSPs, in Proceedings 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS-2017), 2017, pp. 319\u2013330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"ref46","unstructured":"A. A. Bulatov and E. S. Skvortsov, Amalgams of constraint satisfaction problems, in Proceedings 18th International Joint Conference on Artificial Intelligence (IJCAI-2003), 2003, pp. 197\u2013202."},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/BF01214702"},{"key":"ref48","volume-title":"Symbolic Projection for Image Information Retrieval and Spatial Reasoning","author":"Chang S.-K.","year":"1996"},{"key":"ref49","volume-title":"Lecture Notes on Stability Theory","author":"Chernikov A.","year":"2019"},{"key":"ref50","unstructured":"A. G. Cohn, J. Renz, and M. Sridhar, Thinking inside the box: A comprehensive spatial representation for video analysis, in Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR-2012), 2012."},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90087-2"},{"key":"ref52","unstructured":"P. Denis and P. Muller, Predicting globally-coherent temporal structures from texts via endpoint inference and graph decomposition, in Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011), 2011, pp. 1788\u20131793."},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-004-5899-8"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.08.009"},{"key":"ref55","first-page":"7","volume":"50","author":"Dylla F.","year":"2017","journal-title":"ACM Comput. Surv."},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1145\/4904.4999"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1080\/02693799608902079"},{"key":"ref59","unstructured":"M. Gavanelli, A. Passantino, and G. Sciavicco, Deciding the consistency of branching time interval networks, in Proceedings of the 25th International Symposium on Temporal Representation and Reasoning (TIME-2018), 2018, pp. 12:1\u201312:15."},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1145\/174147.169675"},{"key":"ref61","unstructured":"J. Greiner, Complexity of Constraint Satisfaction Problems for Unions of Theories, Ph.D. thesis, Technische Universit\u00e4t Dresden, 2021."},{"key":"ref62","unstructured":"H. Guesgen, Spatial Reasoning Based on Allen\u2019s Temporal Logic, Report ICSI TR 89-049, International Computer Science Institute, 1989."},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/7.3.309"},{"key":"ref64","volume-title":"A Shorter Model Theory","author":"Hodges W.","year":"1997"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00031-9"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0503-1"},{"key":"ref68","doi-asserted-by":"crossref","unstructured":"P. G. Kolaitis and M. Y. Vardi, Conjunctive-query containment and constraint satisfaction, in Proceedings of the 17th Symposium on Principles of Database Systems (PODS-1998), 1998, pp. 205\u2013213.","DOI":"10.1145\/275487.275511"},{"key":"ref69","first-page":"1663","volume":"5","author":"Kompatscher M.","year":"2018","journal-title":"J. Appl. Logics"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00177-8"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876639"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.2307\/2275284"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5384"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009721626239"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1006\/jvlc.1997.9999"},{"key":"ref76","doi-asserted-by":"crossref","unstructured":"G. Ligozat, When tables tell it all: Qualitative spatial and temporal reasoning based on linear orderings, in Proceedings of the 5th International Conference on Spatial Information Theory (COSIT-2001), 2001, pp. 60\u201375.","DOI":"10.1007\/3-540-45424-1_5"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1137\/050634840"},{"key":"ref78","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2122-9"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970037727X"},{"key":"ref80","volume-title":"A Maximally Tractable Fragment of Temporal Reasoning Plus Successor","author":"Mottet A.","year":"2014"},{"key":"ref81","unstructured":"A. Mottet, T. Nagy, M. Pinsker, and M. Wrona, Smooth approximations and relational width collapses, in Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP-2021), 2021, 138."},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2021.6"},{"key":"ref83","doi-asserted-by":"crossref","unstructured":"A. Mottet and M. Pinsker, Smooth approximations and CSPs over finitely bounded homogeneous structures, in Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS-2022), 2022, pp. 36:1\u201336:13.","DOI":"10.1145\/3531130.3533353"},{"key":"ref84","doi-asserted-by":"crossref","unstructured":"L. Mudrov\u00e1 and N. Hawes, Task scheduling for mobile robots using interval algebra, in Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA-2015), 2015, pp. 383\u2013388.","DOI":"10.1109\/ICRA.2015.7139027"},{"key":"ref85","unstructured":"A. Mukerjee and G. Joe, A qualitative model for space, in Proceedings of the 8th National Conference on Artificial Intelligence (AAAI-1990), 1990, pp. 721\u2013727."},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200848"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1137\/0208008"},{"key":"ref88","unstructured":"R. N. Pelavin and J. F. Allen, A model for concurrent actions having temporal extent, in Proceedings of the 6th National Conference on Artificial Intelligence (AAAI-1987), 1987, pp. 246\u2013250."},{"key":"ref89","doi-asserted-by":"crossref","unstructured":"M. Ragni and S. W\u00f6lfl, Branching Allen. Reasoning with intervals in branching time, in Spatial Cognition IV: Reasoning, Action, Interaction, International Conference Spatial Cognition 2004, Lecture Notes in Comput. Sci. 3343, Springer, Berlin, Heidelberg, 2004, pp. 323\u2013343.","DOI":"10.1007\/978-3-540-32255-9_19"},{"key":"ref90","unstructured":"D. A. Randell, Z. Cui, and A. G. Cohn, A spatial logic based on regions and connection, in Proceedings of the 3rd Conference on Principles on Knowledge Representation and Reasoning (KR-1992), 1992, pp. 165\u2013176."},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1016\/j.aei.2012.01.002"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90015-5"},{"key":"ref93","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107415133"},{"key":"ref94","unstructured":"F. Song and R. Cohen, The interpretation of temporal relations in narrative, in Proceedings of the 7th National Conference on Artificial Intelligence (AAAI-1988), 1988, pp. 745\u2013750."},{"key":"ref95","unstructured":"M. Westphal and S. W\u00f6lfl, Qualitative CSP, finite CSP, and SAT: Comparing methods for qualitative constraint-based reasoning, in Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-2009), 2009, pp. 628\u2013633."},{"key":"ref96","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-013-1010-1"},{"key":"ref97","unstructured":"P. Zhang and J. Renz, Qualitative spatial representation and reasoning in Angry Birds: The extended rectangle algebra, in Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR-2014), 2014, pp. 378\u2013387."},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"},{"key":"ref99","doi-asserted-by":"crossref","unstructured":"D. N. Zhuk, A proof of CSP dichotomy conjecture, in Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS-2017), 2017, pp. 331\u2013342.","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1534304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:48Z","timestamp":1787336988000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1534304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,12]]},"references-count":99,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1137\/22M1534304"],"URL":"https:\/\/doi.org\/10.1137\/22m1534304","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,12]]}}}