given D(Xi) has a total complexity in O(d) time for the d possible changes in T **. The**
proof that BC can also be enforced in linear time follows a similar argument. ✷

## 6 A Catalog Of Decompositions Using Range And **Roots**

We have shown how to propagate the Range and Roots **constraints. Specification of** counting and occurrence constraints using Range and Roots **will thus be executable.** Range and Roots **permit us to decompose counting and occurrence global constraints**
into more primitive constraints, each of which having an associated polynomial propagation algorithm. In some cases, such decomposition does not hinder propagation. In other cases, enforcing local consistency on the global constraint is intractable, and decomposition is one method to obtain a polynomial propagation algorithm [13, 15, 14].

In a technical report [9], we present a catalog containing over 70 global constraints from [2] specified with the help of the Range and Roots **constraints. Here we present a**
few of the more important constraints. In the subsequent five subsections, we list some counting and occurrence constraints which can be specified using Range **constraints,**
using Roots constraints, and using both Range and Roots **constraints. We also show** that Range and Roots can be used to specify open **global constraints, a new kind of**
global constraints introduced recently. We finally include problem domains other than counting and occurrence to illustrate the wide range of global constraints expressible in terms of Range and **Roots**.

## 6.1 Applications Of Range **Constraint**

Range **constraints are often useful to specify constraints on the values used by a sequence**
of variables.

## 6.1.1 All Different

The AllDifferent **constraint forces a sequence of variables to take different values**
from each other. Such a constraint is useful in a wide range of problems (e.g. allocation of activities to different slots in a time-tabling problem). It can be propagated efficiently
[25]. It can also be decomposed with a single Range **constraint:**

 $\text{ALLIDIFFERENT}([X_1,..,X_n])\;\text{iff}$  $\text{Range}([X_1,..,X_n],\{1,..,n\},T)\;\wedge\;|T|=n$. 
A special but nevertheless important case of this constraint is the **Permutation**
constraint. This is an AllDifferent constraint where we additionally know R**, the set**
of values to be taken. That is, the sequence of variables is a permutation of the values in R where |R| = n. This also can be decomposed using a single Range **constraint:**
Permutation([X1, .., Xn], R**) iff**
Range([X1, .., Xn], {1, .., n}, R)