The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Tractable constraint languages arising from some algebras that generate congruence distributive varieties

Valeriote, M (McMaster)
Tuesday 31 January 2006, 11:00-12:00

Seminar Room 1, Newton Institute


A consequence of conjectures of Larose-Zadori and of Bulatov is that any constraint language arising from a finite algebra that generates a congruence distributive variety is of bounded relational width and hence is tractable. Some special cases of this have been known for some time, for example, when the algebra has a majority or, more generally, a near unanimity term operation.

A classic theorem of universal algebra (due to Jonsson) is that an algebra generates a congruence distributive variety if and only if it has a sequence of Jonsson terms. In my talk I will discuss the following theorem, produced with Emil Kiss:

Theorem: Let A be a finite algebra that has a sequence of four Jonsson terms. Then the infinite constraint language consisting of all subuniverses of finite powers of A has bounded relational width and hence is globally tractable.


[pdf ]


MP3MP3 Real AudioReal Audio

Back to top ∧