other than v. So, we cannot find a solution of Range in which Xi = v since lb(T **) must**
be covered as well. A value v is removed from D(Yi) in line 1 if i ∈ lb(S**) and** v 6∈ ub(T ).

In this case, Range cannot be satisfied by a tuple where Xi = v. If a value v **is removed**
from ub(T ) in line 1, none of the tuples of values for variables in Y covering lb(T **) can**
cover v as well. Since variables in Y duplicate variables Xi with index in ub(S**), there is**
no hope to satisfy Range if v is in T . Note that ub(T **) cannot be modified in line 1 since**
Y contains only variables Yi for which i was in ub(S). If a value v is added to lb(T **) in**
line 1, this is because there exists i in lb(S) such that D(Yi) ∩ ub(T ) = {v}**. Hence,** v is necessarily in T in all solutions of Range. An index i can be removed from ub(S**) only**
in line 1. This happens when the domain of Yi does not intersect ub(T **). In such a case,**
this is evident that a tuple where i ∈ S could not satisfy Range since Xi **could not take**
a value in T . Finally, if an index i is added to lb(S) in line 1, this is because D(Yi**) is** included in lb(T ), which means that the dummy value has been removed from D(Yi**) in**
line 1. This means that Yi takes a value from lb(T ) in all solutions of Occurs. Xi **also**
has to take a value from lb(T ) in all solutions of **Range**.

Completeness Suppose that a value v is not pruned from D(Xi) after line 1 of PropagRange. If Yi ∈ Y , we know that after line 1 there was an instantiation I on Y and T , solution of Occurs with I[Yi] = v or with Yi = dummy **(thanks to the channelling**
constraints in line 1). We can build the tuple I
′ on X1, ..Xn, S, T where Xi **takes value**
v, every Xj with j ∈ ub(S) and I[Yj ] ∈ I[T ] takes I[Yj ], and the remaining Xj **'s take** any value in their domain. T is set to I[T ] plus the values taken by Xj**'s with** j ∈ lb(S).

These values are in ub(T ) thanks to line 1. Finally, S is set to lb(S**) plus the indices of**
the Yj 's with I[Yj ] ∈ I[T ]. These indices are in ub(S) since the only j**'s removed from** ub(S) in line 1 are such that D(Yj )∩ub(T ) = ∅, which prevents I[Yj **] from taking a value**
in I[T **]. Thus** I
′
is a solution of Range **with** I
′
[Xi] = v**. We have proved that the** Xi's are hybrid consistent after **Propag-Range**.

Suppose a value i ∈ ub(S**) after line 1. Thanks to constraint in line 1 we know there**
exists v in D(Yi) ∩ ub(T ), and so, v ∈ D(Xi) ∩ ub(T ). Now, Xi**is hybrid consistent**
after line 1. Thus Xi = v belongs to a solution of Range**. If we modify this solution by**
putting i in S and v in T **(if not already there), we keep a solution.**
Completeness on lb(S), lb(T ) and ub(T **) is proved in a similar way.**
Complexity. The important thing to notice in Propag-Range **is that constraints in lines**
1–1 are propagated in sequence. Thus, Occurs **is propagated only once, for a complexity**
in O(nd+n· |lb(T )| 3/2). Lines 1, 1, and 1 are in O(nd). Thus, the complexity of PropagRange is in O(nd + n · |lb(T )| 3/2). This reduces to linear time complexity when lb(T **) is**
empty.

Incrementality. The overall complexity over a sequence of restrictions on Xi's, S and T
is in O(n 2d 2). (See incrementality of Occurs **in Section 4.1.)** ✷
Note that the Range constraint can be decomposed using the Gcc **constraint. However, propagation on such a decomposition is in** O(n 2d+n 2.66**) time complexity (see [24]).**
Propag-Range **is thus significantly cheaper.**