The initial domains of Nlu variables also tell us that for every viin V , Nvivi ≥ lvi

. Thus, min(N1(v1−1)) +
min(Nv1v1)+min(N(v1**+1)(**v2−1))+. . .+min(N(vk+1)d) >
n = max(N1d). Successively applying BC on N1v1 =
N1(v1−1)+Nv1v1
, then on N1(v2−1) = N1v1+N(v1**+1)(**v2−1),
and so on until N1d = N1vk + N(vk+1)d will successively increase the minimum of these variables and will lead to a failure on N1d.

We now show that when DC on (6) and BC on (7) and (8)
do not fail, it prunes all values that are pruned when enforcing RC on the GCC constraint. Consider a value v ∈ dom(Xq)
for some q ∈ 1..n such that v does not have any bound support. We derive from [Quimper *et al.*, 2005, Lemmas 1 and 6] that a value v for a variable Xq does not have a bound support on GCC if and only if there exists a set V of values such that either (i) SV =Pw∈V
uw, v ∈ V and range(Xq) is not included in V , or (ii) IV =Pw∈V
lw, v /∈ V and range(Xq)
intersects V . In case (i), V contains v and the values it contains will be taken by too many variables if Xq is in it. In case
(ii), V does not contain v and its values will be taken by not enough variables if Xq is not in it. Consider case (i): Since DC did not fail on (6), by a similar reasoning as above for detecting failure, we derive that V is composed of intervals[l, u]
such that S[l,u] =Pw∈[l,u]
uw. Consider the interval [l, u]
containing v. The greatest value in the initial domain of Nlu was Pw∈[l,u]
uw, which is exactly the number of variables with range included in [l, u] without counting Xq because its range is not included in V . Thus, (7) forces Aqlu = 0 and (6)
prunes value v from dom(Xq) because v ∈ [l, u] by assumption. Consider now case (ii): V = {v1, . . . , vk} is such that IV =Pvi∈V
lvi

. The total number of values taken by the Xi variables being equal to n, the number of variables Xi with range(Xi) not intersecting V is equal to n−Pvi∈V
lvi

, that is S[1,v1−1]+S[v1+1,v2−1]+. . .+S[vk+1,d] = n−Pvi∈V
lvi

.

Thanks to (7), we know that for any l, u, Nlu ≥ S[l,u]
. So, N1(v1−1)+N(v1**+1)(**v2−1)+. . .+N(vk+1)d ≥ n−Pvi∈V
lvi

.

The initial domains of Nlu variables also tell us that for every viin V , Nvivi ≥ lvi

. Thus, min(N1(v1−1)) +
min(Nv1v1)+min(N(v1**+1)(**v2−1))+. . .+min(N(vk+1)d) ≥
n = max(N1d). Successively applying BC on N1v1 =
N1(v1−1)+Nv1v1
, then on N1(v2−1) = N1v1+N(v1**+1)(**v2−1),
and so on until N1vk = N1(vk−1) + Nvkvk will increase all min(N1(vi−1)) and min(N1vi), to the sum of the minimum values of the variables in the right side of each constraint so that min(N1vk

) = min(N1(v1−1))+min(Nv1v1)+
min(N(v1**+1)(**v2−1)) + . . . + min(Nvkvk
). Then, because max(N1d) = n, BC on N1d = N1vk + N(vk+1)d will decrease the maximum value of N1vk and N(vk+1)d to their minimum value, BC on N1vk = N1(vk−1) + Nvkvk will decrease the maximum value of N1(vk−1) and Nvkvk to their minimum value, and so on until all N(vi**+1)(**vi+1−1) are forced to the singleton min(N(vi**+1)(**vi+1−1)) = S[vi+1,vi+1−1].

At this point, (7) forces Aj(vi**+1)(**vi+1−1) = 0 for every variable Xj with range not included in the interval [vi +
1, vi+1 − 1] because that interval is saturated by variables Xp in S[vi+1,vi+1−1], for which Ap(vi**+1)(**vi+1−1) = 1. By assumption value v is not in V , so there exists such an interval
[vi + 1, vi+1 − 1] that contains v. Furthermore, range(Xq)
intersects V , so it is not included in [vi + 1, vi+1 − 1]. Therefore, Aq(vi**+1)(**vi+1−1) is forced to 0 and (6) prunes v from dom(Xq).

There are O(nd2) constraints (6) that can be woken O(d)
times down the branch of the search tree in O(1), so a total of O(nd3) down the branch. There are O(d 2) constraints (7)
which can be woken O(n) times each down the branch for a total cost in O(n) time down the branch. Thus a total of O(nd2). There are O(d 2) constraints (8) that can be woken O(n) times down the branch. Each propagation takes O(1)
time to execute for a total of O(nd2) time down the branch.

The final complexity down the branch of the search tree is therefore O(nd3) + O(nd2) + O(nd2) = O(nd3). ✷
What about bound consistency of the GCC constraint? As in the case of ALL-DIFFERENT, by replacing constraints (6)
by constraints (3) and (4), the decomposition achieves BC. Theorem 4. *Enforcing BC on constraints (3), (4), (7) and*
(8) achieves BC on the corresponding GCC *constraint in* O(nd2) *time down any branch of the search tree.*
Proof: The proof follows that for Theorem 3 except that fixing Ailu = 0 prunes the bounds of dom(Xi) if and only if exactly one bound of the domain of Xiintersects the interval
[l, u]. The complexity reduces to O(nd2) as BC on (3) and
(4) is in O(nd2) (see Theorem 2) and BC on (7) and (8) is in O(nd2) (see Theorem 3). ✷
The best known algorithm for BC on GCC runs in O(n)
time at each call [Quimper *et al.*, 2005] and can be awaken O(nd) times down a branch. This gives a total of O(n 2d),
which is greater than the O(nd2) here when n > d. Our decomposition is also interesting because, as we show in the next section, we can use it to combine together propagators.

## 5 Other Global Constraints

Many other global constraints that count variables or values can be decomposed in a similar way. For example, the global constraint SAME([X1, . . . , Xn], [Y1, . . . , Yn]) is satisfied if and only if the Yi variables are a permutation of the Xi variables. A monolithic flow-based propagator for this constraint is given in [Beldiceanu *et al.*, 2004]. The following decomposition encodes the SAME constraint where 1 ≤ i ≤ n, 1 ≤ l ≤ u ≤ d, l ≤ k and k < u:

Ailu = 1 ⇐⇒ Xi ∈ [l, u], Bilu = 1 ⇐⇒ Yi ∈ [l, u] Nlu =Pn i=1 Ailu, Nlu =Xn i=1 Bilu N1u = N1k + N(k+1)u
This decomposition can be obtained by posting decompositions for EGCC([X1, . . . , Xn], [O1, . . . , Om]) and EGCC([Y1, . . . , Yn], [O1, . . . , Om]) and eliminating common sub-expressions (EGCC is an extended form of the GCC
constraint in which upper and lower bounds on occurrences of values are replaced by integer variables). This is another argument in favor of decompositions since it allows constraints to share "internal" state through common intermediate variables. Such sharing can increase propagation.