D
dp 3
(X4) = [4, 6] and D
dp 3
(X5) = [4, 6]. The interval [4, 6] *is a violated Hall interval* as it contains four variables. We show that Equations (5)–(6) *detect that the interval*
[3, 6] has to be pruned from D(X1).

Consider the pair X1 = 3 and the interval [v, v + k]*, where* v = 3, k = 3*. We* get that B1 1,6 = |{j ∈ {2, 3}|D(Xj ) ⊆ [1, 6]}| = 2 D1 3,6 = |{j ∈ {4, 5})|D(Xj ) ⊆
[3, 6]}| = 2 and B1 1,6 +D1 3,6 = 4 *which is greater than* k = 3*. Hence, the interval* [3, 6]
has to be removed from D(X1).

Theorem 1. *Consider the* ALLDIFFERENT[X1, . . . , Xn] constraint and a set of precedence constraints Xi < Xj *. Enforcing conditions* (5)–(10) *together with bounds consistency on the* ALLDIFFERENT constraint and the precedence constraints is equivalent to enforcing bounds consistency on the ALLDIFFPREC *constraint.*
Proof: Suppose conditions (5)–(10) are fulfilled, ALLDIFFERENT and precedence constraints are bounds consistent and the ALLDIFFPREC constraint is not bounds consistent. Let an assignment of a variable Xito its bound max(Xi) be an unsupported bound. We denote max(Xi) v to simplify notations. We recall that we denoted the domains after direct pruning of Xi = v Ddp v
(X1)*, . . . ,* Ddp v
(Xn). By Lemma 2 the ALLDIFFERENT([X1*, . . . , X*n]) constraint where domains of variables X are Ddp v
(X1)*, . . . ,* Ddp v
(Xn) fails. Hence, there exists a violated Hall interval [*l, u*]
such that |Ddp v
(Xi) ⊆ [l, u]}| > u − l + 1.

Note that direct pruning of Xi = v does not cause the pruning of variables in P(i),
as all precedence constraints are bounds consistent on the original domains. Next we consider several cases depending on the relative position of the value v and the violated Hall interval on the line. Note that the interval [*l, u*] was not a violated Hall interval before the assignment Xi = v. However, due to direct pruning of Xi = v a number of additional variables domains can be forced to be inside [*l, u*]. Hence, we analyze these additional variables and show that conditions (5)–(10) prevent the creation of a violated Hall interval.

Case 1. Suppose v ∈ [*l, u*]. As [*l, u*] is a violated Hall interval, we have that |{j ∈ S(i)|Ddp v
(Xj ) ⊆ [l, u]]}| + |{j /∈ S(i)|Ddp v
(Xj ) ⊆ [l, u]}| > u − l, Note that the number of additional variables that fall into the interval [*l, u*] after setting Xito v consists only of variables that succeed Xi, such that D(Xj ) ⊆ [1, u]. Hence, |{j /∈ S(i)|Ddp v
(Xj ) ⊆ [l, u]}| = |{j /∈ S(i)|D(Xj ) ⊆ [l, u]}|, |{j /∈ S(i)|Ddp v
(Xj ) ⊆
[l, u]}| = |{j ∈ S(i)|D(Xj ) ⊆ [1, u]}| and

## |{J ∈ S(I)|D(Xj ) ⊆ [1, U]}| + |{J /∈ S(I)|D(Xj ) ⊆ [L, U]}| > U − L,

which violate conditions (5)–(7) for v = l and k = u − l.

Case 2. Suppose v /∈ [*l, u*]. If *v > u* + 1 or *v < l* − 1, the assignment Xi = v does not force any extra variables to fall into the interval [*l, u*]. Hence, the interval [*l, u*] is a violated Hall interval before the assignment. This contradicts that ALLDIFFERENT is bounds consistent.

Case 3. Suppose v = u + 1. In this case the assignment Xi = v does not force any additional variables among successors to fall into [*l, u*], as Ddp v
(Xj ) ⊆ [u + 2, d]. Note