CD(4) has bounded width
Carvalho, Catarina, Dalmau, Víctor, Marković, Petar and Maróti, Miklós
(2009)
CD(4) has bounded width.
Algebra Universalis, 60.
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 |
|---|---|
| Identification Number | 10.1007/s00012-009-2113-5 |
| Keywords | math.lo, cs.cc, 68n17 (primary) 08a70, 08b10, 08b05, 03b70, 68t20 (secondary) |
| Date Deposited | 15 May 2025 12:25 |
| Last Modified | 25 Feb 2026 00:27 |