Charles Explorer logo
🇨🇿

The collapse of the bounded width hierarchy

Publikace na Matematicko-fyzikální fakulta |
2016

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

We show that every constraint satisfaction problem (CSP) over a fixed constraint language that has bounded relational width has also relational width (2,3). Together with known results this gives a trichotomy: a CSP has either relational width 1, or relational width (2,3) (and no smaller relational width), or does not have bounded relational width.

A consequence of this result is that if Gamma is a finite constraint language containing relations of arity at most k, then the CSP over Gamma either cannot be solved by a Datalog program, or can be solved by a Datalog program consisting of rules with at most max{3, k} variables and at most 2 variables in the head.