does not remove any value since all domains are already bound consistent (value 2 was considered as possible for X1 **because BC deals with bounds). On the other hand, HC**
removes 4 from D(X2) and from ub(T **) as there does not exist any tuple satisfying** C in which X2 **does not take value 2.**
We will compare local consistency properties applied to (sets of) logically equivalent constraints, c1 and c2. As in [17], a local consistency property Φ on c1 **is as strong as** Ψ on c2 iff, given any domains, if Φ holds on c1 then Ψ holds on c2; Φ on c1 **is stronger** than Ψ on c2 iff Φ on c1 is as strong as Ψ on c2 but not vice versa; Φ on c1 **is equivalent** to Ψ on c2 iff Φ on c1 is as strong as Ψ on c2 and vice versa; Φ on c1 **is incomparable to** Ψ on c2 iff Φ on c1 is not as strong as Ψ on c2 **and vice versa.**
A total function F from a source set S into a target set T is denoted by F : **S −→ T** .

The set of all elements in S that have the same image j ∈ T is F
−1(j) = {i : F(i) = j}.

The image of a set S ⊆ S under F is F(S) = Si∈S F(i**), whilst the domain of a set**
T ⊆ T **under** F is F
−1(T ) = Sj∈T F
−1(j**). Throughout, we will view a set of integer**
variables, X1 to Xn as a function X : {1, .., n**} −→** Si=n i=1 D(Xi). That is, X(i**) is the**
value of Xi.

## 3 Two Useful Patterns: Range And **Roots**

Many counting and occurrence constraints can be specified using simple non-global constraints over integer variables (like X ≤ m), simple non-global constraints over set variables (like S1 ⊆ S2 or |S| = k) available in most constraint solvers, and **two special global**
constraints acting on sequences of variables: Range and Roots. Range **captures the**
notion of image of a function and Roots captures the notion of domain. Specification with Range and Roots **is executable. It permits us to decompose other global**
constraints into more primitive constraints.

Given a function X representing a set of integer variables, X1 to Xn, the **Range**
constraint holds iff a set variable T is the image of another set variable S **under** X.

Range([X1, .., Xn], S, T ) iff T = X(S) (that is, T = {Xi| i ∈ S})
The Roots constraint holds iff a set variable S **is the domain of the another set variable**
T **under** X.

Roots([X1, . . . , Xn], S, T **) iff** S = X
−1(T ) (that is, S = {i | Xi ∈ T })
Range and Roots are not exact inverses. A Range constraint can hold, but the corresponding Roots constraint may not, and vice versa. For instance, Range([1, 1], {1}, {1})
holds but not Roots([1, 1], {1}, {1}**) since** X
−1(1) = {1, 2}, and Roots([1, 1, 1], {1, 2, 3}, {1, 2})
holds but not Range([1, 1, 1], {1, 2, 3}, {1, 2}) as no Xi**is assigned to 2.**
Before showing how to propagate Range and Roots **efficiently, we give two examples**
that illustrate how some counting and occurrence global constraints from [2] can be specified using Range and **Roots**.

The NValue **constraint counts the number of distinct values used by a sequence of**
variables [22, 8, 7]. NValue([X1, .., Xn], N) holds iff N = |{Xi| 1 ≤ i ≤ n}|**. A way to**
implement this constraint is with a Range **constraint:**