Propagators. **Propagators serve here as implementations of constraints. They**
are sometimes also referred to as constraint narrowing operators or filter functions. A propagator is a function p ∈ Dom → Dom **that is contracting (**p(d) ⊆ d)
and monotone (d
′ ⊆ d ⇒ p(d
′) ⊆ p(d**)). Idempotence is not required.**
Propagators are contracting, they only remove values from variable domains.

For an assignment a, a propagator p **hence has only two options: accept it** (p({a}) = {a}), or reject it (p({a}) = ∅**). Monotonicity guarantees that if some** domain d contains an assignment a ∈ d that p accepts, then p **will not remove** a from d: a ∈ p(d**). The propagator therefore behaves like a characteristic function**
for the set of accepted assignments. This set is the **associated constraint of** p.

We say that a propagator p **implements its associated constraint** cp = {a ∈
Asn | p({a}) = {a}}. Monotonicity implies that for any domain d**, we have**
dom(cp ∩ d) ⊆ p(d): no solution of cp is ever removed by p**. We say that** p is sound for any c ⊆ cp and weakly complete **for any** c
′ ⊇ cp **(meaning that**
it accepts all assignments in c **and rejects all assignments not in** c
′**). For any**
constraint c, we can find at least one propagator p such that c = cp**. Typically,**
there are several propagators, differing by propagation strength **(see Sect. 3).**
Our definitions of soundness and different notions of completeness **for propagators are based on and equivalent to Benhamou's [2] and Maher's [9]. We**
specify what is computed by constraint propagation and not how**. Approaches**
for performing constraint propagation can be found in [2, 1, 11].

## 3 Views And Derived Propagators

We now introduce our central concepts, views and derived propagators.

A view on a variable x is an injective function ϕx ∈ Val → Val′**, mapping**
values from Val to values from a possibly different set Val′. We lift a family of views ϕx (one for each x ∈ Var **) point-wise to assignments as follows:**
ϕAsn (a)(x) = ϕx(a(x**)). Finally, given a family of views lifted to assignments,**
we define a view ϕ ∈ Con → Con on constraints as ϕ(c) = {ϕAsn(a) | a ∈ c}.

The inverse of that view is defined as ϕ
−(c) = {a ∈ Asn | ϕAsn (a) ∈ c}.

In the implementation, a view on x presents the same interface as x**, but**
applies transformations when a propagator adjusts or accesses **the domain of** x through the view. In our model, ϕ **performs the transformations for accessing,** and ϕ
− **for adjusting the variable domains. Views can now be composed with a**
propagator: a derived propagator is defined as ϕb(p)(d) = ϕ
−(p(ϕ(d**))), or, using**
function composition, as ϕb(p) = ϕ
− ◦ p ◦ ϕ.

Example. Given a propagator p for the constraint c ≡ (x = y**), we want to**
derive a propagator for c
′ ≡ (x = 2y) using a view ϕ **such that** ϕ
−(c) = c
′.

It is usually easier to think about the other direction: ϕ(c
′) ⊆ c**. Intuitively,**
the function ϕ leaves x as it is and scales y **by 2, while** ϕ
− **does the inverse**
transformation. We thus define ϕx(v) = v and ϕy(v) = 2v**. We have a subset**
relation because some tuples of c may be ruled out by ϕ**. For instance, with** ϕ defined as above, there is no assignment a such that ϕAsn(a)(y**) = 3, but the**
assignment (x 7→ 3, y 7→ **3) is in** c.