Skip to content

LAA

Seminar

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

Abstract

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.

Presentation

[pdf ]

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧