[BeldiceanuContejean94]

$\mathrm{𝚊𝚖𝚘𝚗𝚐}(\mathrm{𝙽𝚅𝙰𝚁},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂})$

$\mathrm{𝚋𝚎𝚝𝚠𝚎𝚎𝚗}$.

The $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint holds since exactly 3 values of the collection of variables $\langle 4,5,5,4,1\rangle$ belong to the set of values $\{1,5,8\}$.

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• Items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ are permutable.

• An occurrence of a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ that belongs to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ (resp. does not belong to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$) can be replaced by any other value in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ (resp. not in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$).

A similar constraint called $\mathrm{𝚋𝚎𝚝𝚠𝚎𝚎𝚗}$ was introduced in CHIP in 1990.

The $\mathrm{𝚌𝚘𝚖𝚖𝚘𝚗}$ constraint can be seen as a generalisation of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint where we allow the $\mathrm{𝚟𝚊𝚕}$ attributes of the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection to be domain variables.

A generalisation of this constraint when the values of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ are not initially fixed is called $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚟𝚊𝚛}$.

When the variable $\mathrm{𝙽𝚅𝙰𝚁}$ (i.e., the first argument of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint) does not occur in any other constraints of the problem, it may be operationally more efficient to replace the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint by an $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ constraint where $\mathrm{𝙽𝚅𝙰𝚁}$ is replaced by the corresponding interval $[\underline{\mathrm{𝙽𝚅𝙰𝚁}},\overline{\mathrm{𝙽𝚅𝙰𝚁}}]$. This stands for two reasons:

• First, by using an $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ constraint rather than an $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint, we avoid the filtering algorithm related to $\mathrm{𝙽𝚅𝙰𝚁}$.

• Second, unlike the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint where we need to fix all its variables to get entailment, the $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ constraint can be entailed before all its variables get fixed. As a result, this potentially avoid unnecessary calls to its filtering algorithm.

A filtering algorithm achieving arc -consistency was given by Bessière et al. in [BessiereHebrardHnichKiziltanWalsh05ERCIM], [BessiereHebrardHnichKiziltanWalsh06ERCIM].

among in Choco, among in JaCoP.

common keyword: $\mathrm{𝚊𝚛𝚒𝚝𝚑}$, $\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}$, $\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}$ (value constraint), $\mathrm{𝚌𝚘𝚞𝚗𝚝}$ (counting constraint), $\mathrm{𝚌𝚘𝚞𝚗𝚝𝚜}$ (value constraint,counting constraint), $\mathrm{𝚍𝚒𝚜𝚌𝚛𝚎𝚙𝚊𝚗𝚌𝚢}$, $\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$, $\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$, $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ (counting constraint).

generalisation: $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚟𝚊𝚛}$ ($\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$).

implies: $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚟𝚊𝚛}$, $\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}$.

related: $\mathrm{𝚛𝚘𝚘𝚝𝚜}$ (can be used for expressing $\mathrm{𝚊𝚖𝚘𝚗𝚐}$), $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}\_\mathrm{𝚌𝚊𝚛𝚍}\_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}$ (counting constraint on maximal sequences).

shift of concept: $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚜𝚎𝚚}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$ and constraint applied in a sliding way), $\mathrm{𝚌𝚘𝚖𝚖𝚘𝚗}$.

soft variant: $\mathrm{𝚘𝚙𝚎𝚗}\_\mathrm{𝚊𝚖𝚘𝚗𝚐}$ (open constraint).

specialisation: $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚍𝚒𝚏𝚏}\_\mathtt{0}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ different from 0), $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$), $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$), $\mathrm{𝚊𝚖𝚘𝚗𝚐}\_\mathrm{𝚖𝚘𝚍𝚞𝚕𝚘}$ (list of $\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$ replaced by list of $\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$ $𝚟$ such that $𝚟\mathrm{mod}\mathrm{𝚀𝚄𝙾𝚃𝙸𝙴𝙽𝚃}$ = $\mathrm{𝚁𝙴𝙼𝙰𝙸𝙽𝙳𝙴𝚁}$), $\mathrm{𝚎𝚡𝚊𝚌𝚝𝚕𝚢}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$ and $\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$ replaced by one single $\mathrm{𝚟𝚊𝚕𝚞𝚎}$).

system of constraints: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ (count the number of occurrences of different values).

used in graph description: $\mathrm{𝚒𝚗}$.

uses in its reformulation: $\mathrm{𝚌𝚘𝚞𝚗𝚝}$.

characteristic of a constraint: automaton, automaton with counters, non-deterministic automaton.

constraint network structure: alpha-acyclic constraint network(2), Berge-acyclic constraint network.

constraint type: value constraint, counting constraint.

filtering: arc-consistency, SAT.

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

The arc constraint corresponds to the unary constraint $\mathrm{𝚒𝚗}(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}.\mathrm{𝚟𝚊𝚛},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂})$ defined in this catalogue. Since this is a unary constraint we employ the $\mathrm{𝑆𝐸𝐿𝐹}$ arc generator in order to produce an initial graph with a single loop on each vertex.

Parts (A) and (B) of Figure 5.16.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐍𝐀𝐑𝐂}$ graph property, the loops of the final graph are stressed in bold.

Figure 5.16.1. Initial and final graph of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint

(a)	(b)

Figure 5.16.2 depicts a first automaton that only accepts all the solutions of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form ${\mathrm{𝚅𝙰𝚁}}_i\in \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ already encountered. To each variable ${\mathrm{𝚅𝙰𝚁}}_i$ of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a 0-1 signature variable ${𝚂}_i$. The following signature constraint links ${\mathrm{𝚅𝙰𝚁}}_i$ and ${𝚂}_i$: ${\mathrm{𝚅𝙰𝚁}}_i\in \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\iff {𝚂}_i$. The automaton counts the number of variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection that take their value in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ and finally assigns this number to $\mathrm{𝙽𝚅𝙰𝚁}$.

Figure 5.16.2. Automaton (with a counter) of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint

Figure 5.16.3. Hypergraph of the reformulation corresponding to the automaton (with a counter) of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint: since all states variables are fixed to the unique state of the automaton, the transitions constraints share at most one variable and the constraint network is Berge-acyclic

We now describe a second counter free automaton that also only accepts all the solutions of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint. Without loss of generality, assume that the collection of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ contains at least one variable (i.e., $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|\ge 1$). Let $n$ and $𝒟$ respectively denote the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, and the union of the domains of the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. Clearly, the maximum number of variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ that are assigned a value in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ cannot exceed the quantity $m=min(n,\overline{\mathrm{𝙽𝚅𝙰𝚁}})$. The $m+2$ states of the automaton that only accepts all the solutions of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint can be defined in the following way:

• We have an initial state labelled by $s_0$.

• We have $m$ intermediate states labelled by $s_i$ $(1\le i\le m)$. The intermediate states are indexed by the number of already encountered satisfied constraints of the form ${\mathrm{𝚅𝙰𝚁}}_k\in \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ from the initial state $s_0$ to the state $s_i$.

• We have a final state labelled by $s_F$.

Three classes of transitions are respectively defined in the following way:

1. There is a transition, labeled by $j$, $(j\in 𝒟\setminus \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂})$, from every state $s_i$, $(i\in [0,m\left]\right)$, to itself.

2. There is a transition, labeled by $j$, $(j\in \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂})$, from every state $s_i$, $(i\in [0,m-1\left]\right)$, to the state $s_{i+1}$.

3. There is a transition, labelled by $i$, from every state $s_i$, $(i\in [0,m\left]\right)$, to the final state $s_F$.

This leads to an automaton that has $m·\left|𝒟\right|+|𝒟\setminus \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|+m+1$ transitions. Since the maximum value of $m$ is equal to $n$, in the worst case we have $n·\left|𝒟\right|+|𝒟\setminus \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|+n+1$ transitions.

Figure 5.16.4 depicts a counter free non deterministic automaton associated with the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint under the hypothesis that (1) all variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are assigned a value in $\{0,1,2,3\}$, (2) $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|$ is equal to 3, (3) $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ corresponds to odd values. The sequence ${\mathrm{𝚅𝙰𝚁}}_1,{\mathrm{𝚅𝙰𝚁}}_2,...,{\mathrm{𝚅𝙰𝚁}}_{\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|},\mathrm{𝙽𝚅𝙰𝚁}$ is passed to this automaton. A state $s_i$ $(1\le i\le 3)$ represents the fact that $i$ odd values were already encountered, while $s_F$ represents the final state. A transition from $s_i$ $(1\le i\le 3)$ to $s_F$ is labelled by $i$ and represents the fact that we can only go in the final state from a state that is compatible with the total number of odd values enforced by $\mathrm{𝙽𝚅𝙰𝚁}$. Note that non determinism only occurs if there is a non -empty intersection between the set of potential values that can be assigned to the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ and the potential value of the $\mathrm{𝙽𝚅𝙰𝚁}$. While the counter free non deterministic automaton depicted by Figure 5.16.4 has 5 states and 18 transitions, its minimum -state deterministic counterpart shown in Figure 5.16.5 has 7 states and 23 transitions.

Figure 5.16.4. Counter free non deterministic automaton of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$$(\mathrm{𝙽𝚅𝙰𝚁},\langle {\mathrm{𝚅𝙰𝚁}}_1,{\mathrm{𝚅𝙰𝚁}}_2,{\mathrm{𝚅𝙰𝚁}}_3\rangle ,\langle 1,3\rangle )$ constraint assuming ${\mathrm{𝚅𝙰𝚁}}_i\in [0,3]$ $(1\le i\le 3)$, with initial state $s_0$ and final state $s_F$

Figure 5.16.5. Counter free minimum-state deterministic automaton of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$$(\mathrm{𝙽𝚅𝙰𝚁},\langle {\mathrm{𝚅𝙰𝚁}}_1,{\mathrm{𝚅𝙰𝚁}}_2,{\mathrm{𝚅𝙰𝚁}}_3\rangle ,\langle 1,3\rangle )$ constraint assuming ${\mathrm{𝚅𝙰𝚁}}_i\in [0,3]$ $(1\le i\le 3)$, with initial state $s_0$ and final state $s_F$

We make the following final observation. Since the Symmetries slot of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint indicates that the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable, and since all incoming transitions to any state of the automaton depicted by Figure 5.16.4 are labelled with distinct values, we can mechanically construct from this automaton a counter free deterministic automaton that takes as input the sequence $\mathrm{𝙽𝚅𝙰𝚁}$, ${\mathrm{𝚅𝙰𝚁}}_3$, ${\mathrm{𝚅𝙰𝚁}}_2$, ${\mathrm{𝚅𝙰𝚁}}_1$ rather than the sequence ${\mathrm{𝚅𝙰𝚁}}_1$, ${\mathrm{𝚅𝙰𝚁}}_2$, ${\mathrm{𝚅𝙰𝚁}}_3$, $\mathrm{𝙽𝚅𝙰𝚁}$. This is achieved by respectively making $s_F$ and $s_0$ the initial and the final state, and by reversing each transition.