

![0_image_0.png](0_image_0.png)

The number of states of the final automaton is Q′ = O(dQ2). The total time complexity to enforce DC on the C&LEX(X, Y , REGULAR) constraint is thus O(nT ′), where T
′is the number of transitions of the product automaton. It should be noted that this algorithm is very easy to implement. Once the product automaton is constructed, we encode the REGULAR constraint for it as a set of ternary transition constraints [10].

The third way to propagate the C&LEX(X, Y , REGULAR) constraint is to encode it as a cost REGULAR constraint. W.L.O.G., we assume that there exist only one initial and one final state. Let Gx be the layered graph for REGULAR(X) and Gy be the layered graph for REGULAR(Y ). We replace the final state at n + 1th layer in Gx with the initial state at 0th layer at Gy. Finally, we need to encode LEX(X, Y ) using the layered graph. We recall that the LEX(X, Y ) constraint can be encoded as an arithmetic constraint (d n−1X[1] + **. . .** + d 0X[n] ≤ d n−1Y [1] + **. . .** + d 0Y [n]) or (d n−1X**[1] +**
. . . + d 0X[n] − d n−1Y [1] − **. . .** − d 0Y [n] ≤ 0), where d = |Sn i=1 D(X[i])|.

In turn this arithmetic constraint can be encoded in the layered graph by adding weights on corresponding arcs. The construction for Example 4 is presented in Figure 4. Values in brackets are weights to encode the LEX(X, Y ) constraint. For instance, the arc (sx, 2) has weight 9. The arc corresponds to the first variable with the coefficient d 2, d = 3. It is labeled with value 1. The weight equals 1 × d 2 = 9.

More generally, an arc between the k − 1 th and k th layers labeled with vj is given weight vjd n−k. Note that the weights of arcs that correspond to variables Y are negative. Hence, the C&LEX(X, Y , REGULAR) constraint can be encoded as a cost REGULAR([A, A], [X, Y ], W) constraint, where W is the cost variable, [A, A] are two consecutive automata. W has to be less than or equal to 0. Consider for example the shortest path through the arc (sy, 2). The cost of the shortest path through this arc is 3. Consequently, value 1 can be pruned form the domain of Y [1].

The time complexity of enforcing DC on the cost REGULAR([A, A], [XY ], W) is O(nT ), where d = |Sn i=1 D(X[i])| and T is the number of transitions of A.

1 Again, the use of large integers adds a linear factor to the complexity, so we get O(n 2T ).