## 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.1.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 counterpart: the types $\mathrm{𝚍𝚟𝚊𝚛}$, $\mathrm{𝚜𝚟𝚊𝚛}$, $\mathrm{𝚖𝚟𝚊𝚛}$ and $\mathrm{𝚛𝚟𝚊𝚛}$ are respectively transformed to $\mathrm{𝚒𝚗𝚝}$, $\mathrm{𝚜𝚒𝚗𝚝}$, $\mathrm{𝚖𝚒𝚗𝚝}$ and $\mathrm{𝚛𝚎𝚊𝚕}$.

2. The second step builds a tree of types $𝒯$ by exploring the slot Argument(s) and by developing the compound data types eventually used. The root of this tree is the type $\mathrm{𝚊𝚝𝚘𝚖}$ and represents the name of the global constraint.

3. The third step normalises the tree of types $𝒯$ by first normalising each subtree of $𝒯$ and then by sorting the children of $𝒯$. We assume the following ordering on the different types: $\mathrm{𝚊𝚝𝚘𝚖}\prec \mathrm{𝚒𝚗𝚝}\prec \mathrm{𝚜𝚒𝚗𝚝}\prec \mathrm{𝚖𝚒𝚗𝚝}\prec \mathrm{𝚛𝚎𝚊𝚕}\prec \mathrm{𝚕𝚒𝚜𝚝}\prec \mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$. Let ${𝒯}_{n}$ denote the normalised tree obtained at this third step.

4. Finally the last step tries to reduce the size of the normalised tree ${𝒯}_{n}$ by identifying $k\left(k>1\right)$ childrens of a vertex $v$ of ${𝒯}_{n}$ for which the $k$ subtrees are identical. When such a configuration is identified the $k$ subtrees of $v$ are replaced by one 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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$, $\mathrm{𝚌𝚘𝚞𝚗𝚝}$, $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$, $\mathrm{𝚍𝚒𝚏𝚏𝚗}$, $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ and $\mathrm{𝚜𝚊𝚖𝚎}$.

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{𝚌𝚝𝚛}}_{\mathtt{1}}$ to a constraint ${\mathrm{𝚌𝚝𝚛}}_{\mathtt{2}}$ if and only if the fact that ${\mathrm{𝚌𝚝𝚛}}_{\mathtt{1}}$ holds implies that ${\mathrm{𝚌𝚝𝚛}}_{\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 15 (i.e., $\mathrm{𝚜𝚘𝚛𝚝}$) to 13 (i.e., $\mathrm{𝚜𝚊𝚖𝚎}$) since the fact that a $\mathrm{𝚜𝚘𝚛𝚝}$ constraint holds implies that a $\mathrm{𝚜𝚊𝚖𝚎}$ constraint also holds.