{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T19:11:17Z","timestamp":1774897877849,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T00:00:00Z","timestamp":1774828800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T00:00:00Z","timestamp":1774828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002957","name":"Technische Universit\u00e4t Dresden","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002957","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    A Datalog program\n                    <jats:italic>solves<\/jats:italic>\n                    a constraint satisfaction problem (CSP) if and only if it derives the goal predicate precisely on the unsatisfiable instances of the CSP. There are three Datalog fragments that are particularly important for finite-domain constraint satisfaction:\n                    <jats:italic>arc monadic Datalog<\/jats:italic>\n                    ,\n                    <jats:italic>linear Datalog<\/jats:italic>\n                    , and\n                    <jats:italic>symmetric linear Datalog<\/jats:italic>\n                    , each having good computational properties. We consider the fragment of Datalog where we impose all of these restrictions simultaneously, i.e., we study\n                    <jats:italic>symmetric linear arc monadic (slam) Datalog<\/jats:italic>\n                    . We characterise the CSPs that can be solved by a slam Datalog program as those that have a gadget reduction to a particular Boolean constraint satisfaction problem. We also present exact characterisations in terms of a homomorphism duality (which we call\n                    <jats:italic>unfolded caterpillar duality<\/jats:italic>\n                    ), and in universal-algebraic terms (using known minor conditions, namely the existence of\n                    <jats:italic>quasi Maltsev operations<\/jats:italic>\n                    and\n                    <jats:italic>k<\/jats:italic>\n                    <jats:italic>-absorptive operations of arity<\/jats:italic>\n                    <jats:italic>nk<\/jats:italic>\n                    , for all\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n,k \\ge 1$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>\u2265<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ). Our characterisations also imply that the question whether a given finite-domain CSP can be expressed by a slam Datalog program is decidable.\n                  <\/jats:p>","DOI":"10.1007\/s00224-026-10261-2","type":"journal-article","created":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T18:30:08Z","timestamp":1774895408000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Symmetric Linear Arc Monadic Datalog and Gadget Reductions"],"prefix":"10.1007","volume":"70","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Starke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,3,30]]},"reference":[{"key":"10261_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F.N., Cosmadakis, S.S.: Expressiveness of restricted recursive queries (extended abstract). In: Johnson, D.S. (ed.) Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14\u201317, 1989, Seattle, Washigton, USA, pp. 113\u2013126. ACM (1989)","DOI":"10.1145\/73007.73018"},{"issue":"18","key":"10261_CR2","doi-asserted-by":"publisher","first-page":"1666","DOI":"10.1016\/j.tcs.2008.12.049","volume":"410","author":"A Atserias","year":"2009","unstructured":"Atserias, A., Bulatov, A.A., Dawar, A.: Affine systems of equations and counting infinitary logic. Theoret. Comput. Sci. 410(18), 1666\u20131683 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"10261_CR3","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: Proceedings of Symposium on Foundations of Computer Science (FOCS), pp. 595\u2013603, (2009)","DOI":"10.1109\/FOCS.2009.32"},{"key":"10261_CR4","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pp. 595\u2013603, (2009)","DOI":"10.1109\/FOCS.2009.32"},{"key":"10261_CR5","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M., Willard, R.: Near unanimity constraints have bounded pathwidth duality. In: Proceedings of the 27th ACM\/IEEE Symposium on Logic in Computer Science (LICS), pp. 125\u2013134, (2012)","DOI":"10.1109\/LICS.2012.24"},{"issue":"1","key":"10261_CR6","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s11856-017-1621-9","volume":"223","author":"L Barto","year":"2018","unstructured":"Barto, L., Opr\u0161al, J., Pinsker, M.: The wonderland of reflections. Israel J. Math. 223(1), 363\u2013398 (2018)","journal-title":"Israel J. Math."},{"key":"10261_CR7","unstructured":"Bodirsky, M.: Graph homomorphisms and universal algebra. Lecture Notes (2023). https:\/\/wwwpub.zih.tu-dresden.de\/~bodirsky\/GH-UA.pdf"},{"key":"10261_CR8","unstructured":"Bodirsky, M., Bul\u00edn, J., Starke, F., Wernthaler, M.: The smallest hard trees. Constraints (2022). arxiv:2205.07528"},{"issue":"1","key":"10261_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s00012-007-2026-0","volume":"57","author":"M Bodirsky","year":"2007","unstructured":"Bodirsky, M., Chen, H.: Oligomorphic clones. Algebra Universalis 57(1), 109\u2013125 (2007)","journal-title":"Algebra Universalis"},{"key":"10261_CR10","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Dalmau, V.: Datalog and constraint satisfaction with infinite templates. J. Comput. Syst. Sci. 79, 79\u2013100 (2013). A preliminary version appeared in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201905)","DOI":"10.1016\/j.jcss.2012.05.012"},{"key":"10261_CR11","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1007\/s00493-022-4918-1","volume":"42","author":"M Bodirsky","year":"2022","unstructured":"Bodirsky, M., Starke, F.: Maximal digraphs with respect to primitive positive constructability. Combinatorica 42, 997\u20131010 (2022)","journal-title":"Combinatorica"},{"key":"10261_CR12","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Vucaj, A.: Two-element structures modulo primitive positive constructability. Algebra Universalis 81(20), (2020). Preprint available at ArXiv:1905.12333","DOI":"10.1007\/s00012-020-0647-8"},{"key":"10261_CR13","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, pp. 319\u2013330, (2017)","DOI":"10.1109\/FOCS.2017.37"},{"key":"10261_CR14","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., Krokhin, A., Larose, B.: Dualities for Constraint Satisfaction Problems, pp. 93\u2013124. Springer, Berlin Heidelberg, Berlin, Heidelberg, (2008)","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"10261_CR15","doi-asserted-by":"crossref","unstructured":"Bul\u00edn, J., Krokhin, A.A., Opr\u0161al, J.: Algebraic approach to promise constraint satisfaction. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23\u201326, 2019, pp. 602\u2013613, (2019)","DOI":"10.1145\/3313276.3316300"},{"key":"10261_CR16","doi-asserted-by":"publisher","first-page":"3188","DOI":"10.1016\/j.tcs.2010.05.016","volume":"411","author":"C Carvalho","year":"2010","unstructured":"Carvalho, C., Dalmau, V., Krokhin, A.: CSP duality and trees of bounded pathwidth. Theoret. Comput. Sci. 411, 3188\u20133208 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"10261_CR17","doi-asserted-by":"crossref","unstructured":"Carvalho, C., Dalmau, V., Krokhin, A.A.: Caterpillar duality for constraint satisfaction problems. In: Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24\u201327 June 2008, Pittsburgh, PA, USA, pp. 307\u2013316. IEEE Computer Society, (2008)","DOI":"10.1109\/LICS.2008.19"},{"issue":"6","key":"10261_CR18","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1093\/logcom\/exq030","volume":"21","author":"C Carvalho","year":"2011","unstructured":"Carvalho, C., Dalmau, V., Krokhin, A.A.: Two new homomorphism dualities and lattice operations. J. Log. Comput. 21(6), 1065\u20131092 (2011)","journal-title":"J. Log. Comput."},{"key":"10261_CR19","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 77\u201390, (1977)","DOI":"10.1145\/800105.803397"},{"issue":"3","key":"10261_CR20","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/3134757","volume":"9","author":"H Chen","year":"2017","unstructured":"Chen, H., Larose, B.: Asking the metaquestions in constraint tractability. TOCT 9(3), 11:1-11:27 (2017)","journal-title":"TOCT"},{"key":"10261_CR21","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Linear Datalog and bounded path duality of relational structures. Logic. Methods Comput. Sci. 1(1), (2005)","DOI":"10.2168\/LMCS-1(1:5)2005"},{"key":"10261_CR22","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Egri, L., Hell, P., Larose, B., Rafiey, A.: Descriptive complexity of list h-coloring problems in logspace: A refined dichotomy. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6\u201310, 2015, pp. 487\u2013498. IEEE Computer Society, (2015)","DOI":"10.1109\/LICS.2015.52"},{"key":"10261_CR23","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Larose, B.: Maltsev + Datalog $$\\rightarrow $$ symmetric Datalog. In: Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24\u201327 June 2008, Pittsburgh, PA, USA, pp. 297\u2013306. IEEE Computer Society, (2008)","DOI":"10.1109\/LICS.2008.14"},{"key":"10261_CR24","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Opr\u0161al, J.: Local consistency as a reduction between constraint satisfaction problems, (2023)","DOI":"10.1145\/3661814.3662068"},{"key":"10261_CR25","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Pearson, J.: Closure functions and width 1 problems. In: Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp. 159\u2013173, (1999)","DOI":"10.1007\/978-3-540-48085-3_12"},{"issue":"3","key":"10261_CR26","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1093\/logcom\/exu003","volume":"26","author":"L Egri","year":"2014","unstructured":"Egri, L.: On constraint satisfaction problems below P. J. Log. Comput. 26(3), 893\u2013922 (2014)","journal-title":"J. Log. Comput."},{"key":"10261_CR27","doi-asserted-by":"crossref","unstructured":"Egri, L., Larose, B., Tesson, P.: Symmetric Datalog and constraint satisfaction problems in logspace. In: Proceedings of the Symposium on Logic in Computer Science (LICS), pp. 193\u2013202, (2007)","DOI":"10.1109\/LICS.2007.47"},{"key":"10261_CR28","doi-asserted-by":"crossref","unstructured":"Egri, L., Larose, B., Tesson, P.: Directed st-connectivity is not expressible in symmetric Datalog. In: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7\u201311, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, pp. 172\u2013183, (2008)","DOI":"10.1007\/978-3-540-70583-3_15"},{"key":"10261_CR29","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"10261_CR30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"issue":"4","key":"10261_CR31","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1090\/S0002-9947-96-01537-1","volume":"348","author":"P Hell","year":"1996","unstructured":"Hell, P., Ne\u0161et\u0159il, J., Zhu, X.: Duality and polynomial testing of tree homomorphisms. TAMS 348(4), 1281\u20131297 (1996)","journal-title":"TAMS"},{"key":"10261_CR32","volume-title":"A shorter model theory","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)"},{"issue":"1\u20132","key":"10261_CR33","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency and closure. Artif. Intell. 101(1\u20132), 251\u2013265 (1998)","journal-title":"Artif. Intell."},{"key":"10261_CR34","doi-asserted-by":"crossref","unstructured":"Kanellakis, P.C.: Logic programming and parallel complexity, pp. 547\u2013585. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, (1988). Book chapter in \u2018Foundations of Deductive Databases and Logic Programming\u2019","DOI":"10.1016\/B978-0-934613-40-8.50018-X"},{"key":"10261_CR35","doi-asserted-by":"crossref","unstructured":"Kazda, A.: $$n$$-permutability and linear Datalog implies symmetric Datalog. Logical Methods in Computer Science, vol. 14, Issue 2, (2018)","DOI":"10.23638\/LMCS-14(2:3)2018"},{"issue":"3","key":"10261_CR36","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00012-015-0327-2","volume":"73","author":"M Kozik","year":"2015","unstructured":"Kozik, M., Krokhin, A., Valeriote, M., Willard, R.: Characterizations of several Maltsev conditions. Algebra Univer. 73(3), 205\u2013224 (2015)","journal-title":"Algebra Univer."},{"key":"10261_CR37","doi-asserted-by":"crossref","unstructured":"Larose, B., Loten, C., Tardif, C.: A characterisation of first-order constraint satisfaction problems. Logic. Methods Comput. Sci. 3(4:6), (2007)","DOI":"10.2168\/LMCS-3(4:6)2007"},{"issue":"18","key":"10261_CR38","doi-asserted-by":"publisher","first-page":"1629","DOI":"10.1016\/j.tcs.2008.12.048","volume":"410","author":"B Larose","year":"2009","unstructured":"Larose, B., Tesson, P.: Universal algebra and hardness results for constraint satisfaction problems. Theoret. Comput. Sci. 410(18), 1629\u20131647 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"3\u20134","key":"10261_CR39","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00012-007-2012-6","volume":"56","author":"B Larose","year":"2007","unstructured":"Larose, B., Z\u00e1dori, L.: Bounded width problems and algebras. Algebra Univer. 56(3\u20134), 439\u2013466 (2007)","journal-title":"Algebra Univer."},{"key":"10261_CR40","unstructured":"Meyer, S., Starke, F.: Finite simple groups in the primitive positive constructability poset. (2024)"},{"key":"10261_CR41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-5547-1","volume-title":"Funktionen- und Relationenalgebren","author":"R P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin (1979)"},{"key":"10261_CR42","doi-asserted-by":"crossref","unstructured":"Rossman, B.: Homomorphism preservation theorems. J. ACM 55(3), (2008)","DOI":"10.1145\/1379759.1379763"},{"key":"10261_CR43","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 216\u2013226, (1978)","DOI":"10.1145\/800133.804350"},{"key":"10261_CR44","unstructured":"Starke, F.: Digraphs modulo primitive positive constructability. Preprint,: PhD dissertation. Institute of Algebra, TU Dresden (2024)"},{"key":"10261_CR45","unstructured":"Vucaj, A.: Clones over finite sets and minor conditions. Preprint,: PhD dissertation. Institute of Algebra, TU Dresden (2023)"},{"key":"10261_CR46","doi-asserted-by":"crossref","unstructured":"Vucaj, A., Zhuk, D.: Submaximal clones over a three-element set up to minor-equivalence, (2024)","DOI":"10.1007\/s00012-024-00852-w"},{"issue":"5","key":"10261_CR47","doi-asserted-by":"publisher","first-page":"30:1","DOI":"10.1145\/3402029","volume":"67","author":"D Zhuk","year":"2020","unstructured":"Zhuk, D.: A proof of the CSP dichotomy conjecture. J. ACM 67(5), 30:1-30:78 (2020)","journal-title":"J. ACM"},{"key":"10261_CR48","doi-asserted-by":"crossref","unstructured":"Zhuk, D.N.: A proof of CSP dichotomy conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, pp. 331\u2013342, (2017). arxiv:1704.01914","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10261-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10261-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10261-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T18:30:11Z","timestamp":1774895411000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10261-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,30]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10261"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10261-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,30]]},"assertion":[{"value":"30 March 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"18"}}