If Xl >lex Yu then C&LEX(X, Y , C) does not have a solution and Algorithm 4 fails at line 5. Otherwise, we notice that if Xl ≤lex Yu then Xl and Yu is a solution of C&LEX(X, Y , C), because Xlis a solution of C(X), Yu is a solution of C(Y ) and Xl ≤lex Yu. Consequently, invocation of the simplified version of C&LEX at lines 6 and 7 cannot change Xl and Yu. ⊓⊔
Example 2. We consider how Algorithm 4 works on the first two rows C&LEX constraint from Example 1. Let n equal 5. In this case domains of the first two rows of variables are M[1]
M[2]=
[1, 2, 3, 4] [6, 7, 8, **9] 5**
[1, 2, 3, 4] [5, 6, 7, **8] 4**.

Suppose the solver branches on X**[1] = 1**. Algorithm 4 finds the lexicographically smallest and greatest solutions of M[1] and M[2] using Algorithm 1(line 2).

These solutions are [1, 6, 5] and [4, 8, 4] respectively . Then enforces DC on C&LEXlb([1, 6, 5], M[2], C) in the following way:

1. copies M[2] to LX 2. marks all values that have a support starting with a value greater than 1 (that is 2, 3 and 4). There are three supports that satisfy this condition, namely, [2, 6, 4], [3, 7, 4] and [4, 8, 4]. Checks conditions at line 8 and assigns LX[1] to 1. Then it moves to the next iteration.

3. marks all values that have a support starting with a prefix greater than [1, 6]. There are no such values. Checks conditions at line 8 and assigns LX[2] to 6. Then it moves to the next iteration.

4. marks all values that have a support starting with a prefix greater than [1, 6, 5].

There are no such values. Checks conditions at line 8 and stops the marking part.

5. removes unmarked values: value 1 from X[2] and value 5 from Y [2].
Finally, it enforces DC on C&LEXub(M[1], [4, 8, 4], C). This sets M[1] to [1, 6, 5],
because the solver branched on X**[1] = 1** and [1, 6, 5] is the only possible support for this assignment.

The time complexity of the general algorithm is more expensive than the decomposition into individual constraints C(X), C(Y ) and LEX(X, Y ) by a linear factor.

The general algorithm is not incremental, but its performance can be improved by detecting entailment. If Xu < Yl then the LEX constraint is entailed and C&LEX can be decomposed into two constraints C(X) and C(Y ). Similarly, we can improve the complexity by detecting when C(X) and C(Y ) are entailed. As we show in the next sections, the time complexity of the propagator for the C&LEX(X, Y , C) constraint can also be improved by making it incremental for many common constraints C by exploiting properties of C. Note also that Algorithm 4 easily extends to the case that different global constraints are applied to X and Y .

## 3.2 The C&Lex(**X, Y ,** Sequence) Constraint

In this section we consider the case of a conjunction of the LEX constraint with two SEQUENCE constraints. First we assume that variables X and Y are Boolean variables. Later we will show how to extend this to the general case. In the