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 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.