Barto, Libor; Kozik, Marcin Congruence distributivity implies bounded width. (English) Zbl 1205.68529 SIAM J. Comput. 39, No. 4, 1531-1542 (2009). Summary: We show that a constraint language with compatible Jónsson terms (or, equivalently, associated with an algebra generating a congruence distributive variety) defines a constraint satisfaction problem solvable by the local consistency checking algorithm. Cited in 5 Documents MSC: 68W40 Analysis of algorithms 08A70 Applications of universal algebra in computer science 08B10 Congruence modularity, congruence distributivity 68R10 Graph theory (including graph drawing) in computer science 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) Keywords:constraint satisfaction problem; bounded width; local consistency; congruence distributive variety; Jónsson terms PDFBibTeX XMLCite \textit{L. Barto} and \textit{M. Kozik}, SIAM J. Comput. 39, No. 4, 1531--1542 (2009; Zbl 1205.68529) Full Text: DOI