The Expressive Power of Valued Constraints: Hierarchies and Collapses

Standa Zivny

Oxford University Computing Laboratory

Abstract

In the first part of my talk, I introduce valued constraints and the concept of expressive power. I mention problems I am currently working on. Firstly, an algebraic characterisation of the expressive power of valued constraints. Secondly, the connection between valued constraints and the problem of submodular function minimisation.

In the second part of my talk, I investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. I show that in some cases a large class of valued constraints, of all possible arities, can be expressed by using valued constraints of a fixed finite arity. I also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an