## 3.5. Constraints argument patterns

If you do not know the name of the global constraint you are looking for, but you know the types of its arguments this section allows to find out all global constraints which have similar arguments. For this purpose we associate to each global constraint of the catalogue a unique normalised signature tree derived from the types of its arguments.An informal rule used in the catalogue about the order of the arguments of a constraint is that we usually first mention a domain variable which represents a result computed from one or several collections that occur just after. Finally, eventual parameters are put as the last arguments of the constraint. The purpose of this normalised signature tree is to get a concise normal form of the arguments of a global constraint that does not depend of the order in which these arguments are defined.

The normalisation takes as input the slots Type(s) and Argument(s) of the description of a global constraintSee Section 2.2.4 for the description of these slots. and computes the normalised signature tree in four steps:

1. The first step converts all types related to variables to their corresponding ground counterparts: the types $\mathrm{\pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi }$ and $\mathrm{\pi \pi \pi \pi }$ are respectively transformed to $\mathrm{\pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi }$ and $\mathrm{\pi \pi \pi \pi }$.

2. The second step builds a tree of types $\mathrm{\pi ―}$ by exploring the slot Argument(s) and by developing the compound data types possibly used. The root of this tree is the type $\mathrm{\pi \pi \pi \pi }$ and represents the name of the global constraint.

3. The third step normalises the tree of types $\mathrm{\pi ―}$ by first normalising each subtree of $\mathrm{\pi ―}$ and then by sorting the children of $\mathrm{\pi ―}$. We assume the following ordering on the different types: $\mathrm{\pi \pi \pi \pi }\beta Ί\mathrm{\pi \pi \pi }\beta Ί\mathrm{\pi \pi \pi \pi }\beta Ί\mathrm{\pi \pi \pi \pi }\beta Ί\mathrm{\pi \pi \pi \pi }\beta Ί\mathrm{\pi \pi \pi \pi }\beta Ί\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$. Let ${\mathrm{\pi ―}}_{n}$ denote the normalised tree obtained at this third step.

4. Finally the last step tries to reduce the size of the normalised tree ${\mathrm{\pi ―}}_{n}$ by identifying $k\left(k>1\right)$ children of a vertex $v$ of ${\mathrm{\pi ―}}_{n}$ for which the $k$ subtrees are identical. When such a configuration is identified the $k$ subtrees of $v$ are replaced by a single subtree and the integer $k$ is put as an exponent of $v$.

The three rows of FigureΒ 3.5.1 illustrate respectively the second, third and fourth steps for computing the normalised signature tree associated with the arguments of the constraints $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ and $\mathrm{\pi \pi \pi \pi }$.

The next sections provide for each possible constraints arity all existing normalised signature trees together with the corresponding list of global constraints of the catalogue. The leftmost part of an entry corresponds to a normalised signature tree, while the rightmost upper part gives the corresponding list of global constraints. Finally the rightmost lower part describes the dependency between the constraints of the list: there is an edge from a constraint ${\mathrm{\pi \pi \pi }}_{\mathtt{1}}$ to a constraint ${\mathrm{\pi \pi \pi }}_{\mathtt{2}}$ if and only if the fact that ${\mathrm{\pi \pi \pi }}_{\mathtt{1}}$ holds implies that ${\mathrm{\pi \pi \pi }}_{\mathtt{2}}$ also holds. For instance, consider the constraints associated with the normalised signature tree corresponding to two collections of integers depicted by TableΒ 3.5.1. There is an edge from 16 (i.e., $\mathrm{\pi \pi \pi \pi }$) to 14 (i.e., $\mathrm{\pi \pi \pi \pi }$) since the fact that a $\mathrm{\pi \pi \pi \pi }$ constraint holds implies that a $\mathrm{\pi \pi \pi \pi }$ constraint also holds.