2026-07-24T11:55:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22954 2025-10-02T12:19:34Z ddc:004 open_access

Symmetric Linear Arc Monadic Datalog and Gadget Reductions Bodirsky, Manuel Starke, Florian Datalog Gadget Reductions Homomorphism Dualities Minor Conditions A Datalog program solves 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: arc monadic Datalog, linear Datalog, and symmetric linear Datalog, each having good computational properties. We consider the fragment of Datalog where we impose all of these restrictions simultaneously, i.e., we study symmetric linear arc monadic (slam) Datalog. 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 unfolded caterpillar duality), and in universal-algebraic terms (using known minor conditions, namely the existence of quasi Maltsev operations and k-absorptive operations of arity nk, for all n,k ≥ 1). Our characterisations also imply that the question whether a given finite-domain CSP can be expressed by a slam Datalog program is decidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Florian Starke 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.13 urn:nbn:de:0030-drops-229548 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode