×

Congruence distributivity implies bounded width. (English) Zbl 1205.68529

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.

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.)
PDFBibTeX XMLCite
Full Text: DOI