2006 | OriginalPaper | Buchkapitel
Datalog and Constraint Satisfaction with Infinite Templates
verfasst von : Manuel Bodirsky, Víctor Dalmau
Erschienen in: STACS 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We relate the expressive power of Datalog and constraint satisfaction with infinite templates. The relationship is twofold: On the one hand, we prove that every non-empty problem that is closed under disjoint unions and has Datalog width one can be formulated as a constraint satisfaction problem (CSP) with a countable template that is
ω-categorical
. Structures with this property are of central interest in classical model theory. On the other hand, we identify classes of CSPs that can be solved in polynomial time with a Datalog program. For that, we generalise the notion of the
canonical Datalog program
of a CSP, which was previously defined only for CSPs with finite templates by Feder and Vardi. We show that if the template Γ is
ω
-categorical, then CSP(Γ) can be solved by an (
l
,
k
)-Datalog program if and only if the problem is solved by the canonical (
l
,
k
)-Datalog program for Γ. Finally, we prove algebraic characterisations for those
ω
-categorical templates whose CSP has Datalog width (1,
k
), and for those whose CSP has strict Datalog width
l
.
Topic:
Logic in Computer Science, Computational Complexity.