CD(4) has bounded width
Carvalho, Catarina, Dalmau, Víctor, Marković, Petar and Maróti, Miklós
(2009)
CD(4) has bounded width.
pp. 293-297.
ISSN 1420-8911
We prove that the constraint languages invariant under a short sequence of J\'onsson terms (containing at most three non-trivial ternary terms) are tractable by showing that they have bounded width. This improves the previous result by Kiss and Valeriote and presents some evidence that the Larose-Zadori conjecture holds in the congruence-distributive case.
| Item Type | Article |
|---|---|
| Uncontrolled Keywords | math.LO; cs.CC; 68N17 (Primary) 08A70, 08B10, 08B05, 03B70, 68T20 (Secondary) |
| Date Deposited | 14 Nov 2024 10:50 |
| Last Modified | 14 Nov 2024 10:50 |