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
Copy

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
Keywords math.lo, cs.cc, 68n17 (primary) 08a70, 08b10, 08b05, 03b70, 68t20 (secondary)
Date Deposited 15 May 2025 12:25
Last Modified 30 May 2025 23:50

Explore Further

visibility_off picture_as_pdf
picture_as_pdf
CCarvalho3.pdf
subject
Submitted Version
lock
Restricted to Repository staff only
Request Copy

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads