Symmetric Linear Arc Monadic Datalog and Gadget Reductions
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
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.
Details
| Originalsprache | Englisch |
|---|---|
| Titel | 28th International Conference on Database Theory, ICDT 2025 |
| Redakteure/-innen | Sudeepa Roy, Ahmet Kara |
| Herausgeber (Verlag) | Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing |
| Seiten | 13:1-13:20 |
| ISBN (elektronisch) | 9783959773645 |
| Publikationsstatus | Veröffentlicht - 21 März 2025 |
| Peer-Review-Status | Ja |
Publikationsreihe
| Reihe | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Band | 328 |
| ISSN | 1868-8969 |
Konferenz
| Titel | Joint Conference of the 28th International Conference on Extending Database Technology & the 28th International Conference on Database Theory |
|---|---|
| Kurztitel | EDBT/ICDT 2025 |
| Veranstaltungsnummer | 28 |
| Dauer | 25 - 28 März 2025 |
| Webseite | |
| Ort | Universitat Politècnica de Catalunya (UPC) |
| Stadt | Barcelona |
| Land | Spanien |
Externe IDs
| ORCID | /0000-0001-8228-3611/work/208071912 |
|---|
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Datalog, Gadget Reductions, Homomorphism Dualities, Minor Conditions