2.3.1 Non-Basic Constraints

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

Equality
or
Ordering, e.g.

Arithmetic, e.g.

Set, e.g.
$S_1\subseteq S_2$	subset
$S_1\parallel S_2$	disjointness
$S_3=S_1\cup S_2$	union
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$	$\rightarrow$	$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$	$\rightarrow$	$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.