G.: Bound consistency for binary length-lex set constraints

The length-lex representation has been recently proposed for representing sets in Constraint Satisfaction Problems. The length-lex representation directly captures cardinality infor-mation, provides a total ordering for sets, and allows bound consistency on unary constraints to be enforced in time Õ(c), where c is the cardinality of the set. However, no algo-rithms were given to enforce bound consistency on binary constraints. This paper addresses this open issue. It presents algorithms to enforce bound consistency on disjointness and cardinality constraints in time O(c3). Moreover, it presents a generic bound-consistency algorithm for any binary con-straint S which requires Õ(c2) calls to a feasibility subrou-tine for S