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



Constraint satisfaction problems and dualities

Krokhin, A (Durham)
Monday 06 March 2006, 11:00-12:00

Seminar Room 1, Newton Institute


We consider constraint satisfaction (or homomorphism) problems of the form CSP(B): given a structure A, is there a homomorphism from A to a fixed structure B? The concept of duality for CSPs is based on the idea of providing an obstruction set (of structures) for homomorphism to B. There exist several types of duality according to the properties of obstruction sets. In this talk, we will review three main types of duality and discuss the problem of characterising structures with a given type of duality.


[pdf ] [ps  ]


MP3MP3 Real AudioReal Audio

Back to top ∧