2.4.1 Propagation

Propagation is saturation under deterministic inference. The basic inference rules as well the inference rules corresponding to the non-basic constraints are applied repeatedly until a fix point is reached, i.e. until the partial information about the assignment can no longer be improved. At this point, there are 3 possibilities:

  1. \textbf{false} was derived, i.e. we have arrived at a contradiction and this branch of the search must be abandoned since it cannot lead to a solution.

  2. All variables are determined: the assignment is fully known and satisfies the constraints. This is a solution.

  3. At least one variable is not yet determined. At this point we need search and non-deterministically apply a distribution rule.


Denys Duchier
Version 1.2.0 (20010221)