
## 3.2 Correctness Of Derived Propagators

Derived propagators are well-defined and correct: a derived propagator ϕb(p) is in fact a propagator, and it induces the desired constraint (cϕb(p) = ϕ
−(cp)). The proofs of these statements employ the following direct consequences of the definitions of views:
P1. ϕ and ϕ
− are monotonic by construction (as ϕ and ϕ
− are defined point-wise).

P2. ϕ
− ◦ϕ = id (the identity function, as ϕ is injective).

P3. |ϕ({a})| = 1, ϕ(/0) = /0.

P4. For any view ϕ and domain d ∈ Dom, we have ϕ(d) ∈ Dom′, and for any d
′ ∈
Dom′, we have ϕ
−(d
′) ∈ Dom (as views are defined point-wise).
Proposition 1 (Correctness) For a propagator p and view ϕ, ϕb(p) is a propagator. ∗
Proof. The derived propagator is well-defined because both ϕ(d) and ϕ
−(d) are domains (see P4 above). We have to show that ϕ
− ◦ p ◦ϕ is contracting and monotonic.

For contraction, we have p(ϕ(d)) ⊆ ϕ(d) as p is contracting. From monotonicity of ϕ
− (with P1), it follows that ϕ
−(p(ϕ(d))) ⊆ ϕ
−(ϕ(d)). As ϕ
− ◦ϕ = id (with P2),
we have ϕ
−(p(ϕ(d))) ⊆ d, which proves that ϕb(p) is contracting.

Monotonicity is shown as follows for all domains d
′,d with d
′ ⊆ d:
ϕ(d
′) ⊆ ϕ(d) (ϕ monotonic, P1)
=⇒ p(ϕ(d
′)) ⊆ p(ϕ(d)) (p monotonic)
=⇒ ϕ
−(p(ϕ(d
′))) ⊆ ϕ
−(p(ϕ(d))) (ϕ
− monotonic, P1)
In summary, for any propagator p, ϕb(p) = ϕ
− ◦ p ◦ϕ is a propagator.

Non-monotonic propagators as defined in [34] must at least be *weakly* monotonic, which means that p({a}) ⊆ p(d) for all domains d and assignments a ∈ d. The above proof can be easily adjusted to weakly monotonic propagators by replacing d
′ with {a}
and using P3 in the second line of the proof.

Proposition 2 (Induced constraints) Let p be a propagator, and let ϕ be a view.

Then ϕb(p) induces the constraint ϕ
−(cp). ∗
Proof. As p induces cp, we know p({a}) = cp ∩ {a} for all assignments a. With |ϕ({a})| = 1 (P3), we have p(ϕ({a})) = cp ∩ ϕ({a}). Furthermore, we know that cp ∩ϕ({a}) is either /0 or ϕ({a}).

- Case /0: We have ϕ
−(p(ϕ({a}))) = /0 =
a
′ ∈ Asn
 a = a
′ ∧ϕAsn(a) ∈ cp
	=
ϕ
−(cp)∩ {a}.

- *Case* ϕ({a}): With P2, we have ϕ
− ◦ϕ = id and hence ϕ
−(p(ϕ({a}))) = {a}.

Furthermore, ϕ
−(cp)∩ {a} =
a
′ ∈ Asn
 a = a
′ ∧ϕAsn(a) ∈ cp
	= {a}.
Together, this shows that ϕ
− ◦ p ◦ϕ({a}) = {a} ∩ϕ
−(cp).

Another important property is that views preserve contraction: if a propagator p prunes a domain, the pruning will not be lost after transformation by ϕ
−.

Proposition 3 (Views preserve contraction) Let p be a propagator, let ϕ be a view, and let d be a domain such that p(ϕ(d)) ⊂ ϕ(d). Then ϕb(p)(d) ⊂ d. ∗