2.3.1 Non-Basic Constraints

A constraint programming system typically provides a rich set of non-basic constraints, such as:


I_1=I_2 or S_1=S_2


Ordering, e.g.



Arithmetic, e.g.



Set, e.g.

S_1\subseteq S_2


S_1\parallel S_2


S_3=S_1\cup S_2


Membership, e.g.

I\in S


and many more. The operational semantics of each non-basic constraint is specified by a collection of inference rules.

For example, the disjointness constraint S_1\parallel
S_2 corresponds to the two inference rules below:

S_1\parallel S_2\wedge
S_1\subseteq D_1\wedge
D_2\subseteq S_2


S_1\subseteq D_1\setminus D_2

S_1\parallel S_2\wedge
D_1\subseteq S_1\wedge
S_2\subseteq D_2


S_2\subseteq D_2\setminus D_1

i.e. all elements known to be in S_2 cannot possibly be in S_1 and vice versa.

A challenge that must be faced by every user of a constraint programming system is then to express a CSP's constraints in terms of non-basic constraints available in the system. Fortunately, Mozart has a very rich set of constraints (see [DKM+99]) that facilitate the task.

Denys Duchier
Version 1.2.0 (20010221)