6.3 Constraints And Propagators

A constraint which is more complicated than basic constraints cannot be directly represented in the store. Instead it is represented by a propagator. A propagator is a concurrent agent that observes the store and tries to improve the information in it according to the semantics of the constraint it represents. A propagator has the declarative semantics of the constraint it represents and operational semantics that are described by inference rules.

As an example, consider the disjointness constraint S_1\PAR S_2. Its declarative semantics is that it is satisfied only in models where S_1 and S_2 denote disjoint sets. The operational semantics of the propagator can be specified by the following two inference rules:

\begin{array}{r@{\quad\rightarrow\quad}l}
S_1\PAR S_2\ \wedge\ i\in S_1& i\not\in S_2\\
S_1\PAR S_2\ \wedge\ i\in S_2& i\not\in S_1
\end{array}

i.e. if an integer i is known to be in S_1 then it must be excluded from S_2, and reciprocally. A propagator is supposed to notice as soon as possible whether its constraint is entailed by the store. For example, if the upper bounds of S_1 and S_2 are disjoint, then the sets are necessarily disjoint. In such a case, the propagator disappears since its constraint is satisfied and it will no longer be able to improve the information in the store.


Denys Duchier
Version 1.2.0 (20010221)