only if d is stronger than d
′and d(x) ⊂ d
′(x) for some variable x. The goal of constraint propagation is to prune values from variable domains, thus inferring stronger domains, without removing solutions of the constraints.

A propagator is a function p that takes a domain as its argument and returns a stronger domain, it may only *prune* assignments. If the original domain is an assigned domain {a}, the propagator either accepts (p({a}) = {a}) or rejects (p({a}) = /0) it, realizing a *decision procedure* for its constraint. The pruning and the decision procedure must be consistent: if the decision procedure accepts an assignment, the pruning procedure must never remove this assignment from any domain. This property is enforced by requiring propagators to be monotonic.

Definition 4 (Propagators) A *propagator* is a function p ∈ Dom → Dom that is
- *contracting: p*(d) ⊆ d for any domain d;
- *monotonic: p*(d
′) ⊆ p(d) for any domains d
′ ⊆ d.

The set of all propagators is Prop. If a propagator p returns a *strictly* stronger domain
(p(d) ⊂ d), we say that *p prunes the domain d*. The propagator *p induces* the unique constraint cp defined by the set of assignments accepted by p:

## Cp = {A ∈ Asn | P({A}) = {A}} ∗

Propagators can also be *idempotent* (p(p(d)) = p(d) for any domain d). Idempotency is not required to make propagation sound or complete, but it can make propagation more efficient [33]. Like idempotency, monotonicity as defined here is not necessary for soundness or completeness of a solver [34]. Most definitions and theorems in this paper are independent of whether propagators are monotonic or not. Nonmonotonicity will thus only be discussed where it is relevant.

Propagation strength. Each propagator induces a single constraint, but different propagators can induce the same constraint, differing in *strength*. Typical examples are propagators for the *all-different* constraint that perform naive pruning when variables are assigned, or establish bounds consistency [26] or domain consistency [30].

In the literature, propagation strength is usually defined as a property of a domain in relation to a constraint. For example, a domain d is *domain-consistent* (also known as generalized arc-consistent) with respect to a constraint c if d(x) only contains values that appear in at least one solution of c for each variable x. As this paper is concerned with propagators, propagation strength is defined with respect to a propagator.

A propagator p is *domain-complete* if any domain it returns is domain-consistent with respect to cp. For any constraint c, there is exactly one domain-complete propagator for c (as domains form a lattice). It is defined as ˆpc(d) = dom(cp ∩d), where dom(c) is the *domain relaxation* of c, the strongest domain that contains all assignments of c, dom(c) = min{d | c ⊆ d}.

For constraints over integer variables (V ⊆ Z), several weaker notions of propagation strength are known. The most well-known is *bounds consistency*, which in fact can mean one of four special cases: range, bounds(D), bounds(Z), and bounds(R)
consistency (as discussed in [7, 28]).

The first three differ in whether holes are ignored in the original domain, in the resulting domain, or in both, in that order. Holes in a domain are ignored by the function hull(d)(x) = [min(d(x)) .. max(d(x))], which returns the convex hull of a variable