Figure 5.355.2 depicts a first automaton that only accepts all the solutions to the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form $\left(\right|{\mathrm{𝚅𝙰𝚁}}_i-{\mathrm{𝚅𝙰𝚁}}_{i+1}\left|\right)>\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}$ already encountered. To each pair of consecutive variables $({\mathrm{𝚅𝙰𝚁}}_i,{\mathrm{𝚅𝙰𝚁}}_{i+1})$ of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a 0-1 signature variable $S_i$. The following signature constraint links ${\mathrm{𝚅𝙰𝚁}}_i$, ${\mathrm{𝚅𝙰𝚁}}_{i+1}$ and $S_i$: $\left(\right|{\mathrm{𝚅𝙰𝚁}}_i-{\mathrm{𝚅𝙰𝚁}}_{i+1}\left|\right)>\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}\iff S_i=1$.

Figure 5.355.2. Automaton (with one counter) of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint and its glue matrix

Figure 5.355.3. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint

Since the reformulation associated with the previous automaton is not Berge-acyclic, we now describe a second counter free automaton that also only accepts all the solutions to the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint. Without loss of generality, assume that the collection of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ contains at least two variables (i.e., $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|\ge 2$). Let $n$, $\mathrm{𝑚𝑖𝑛}$, $\mathrm{𝑚𝑎𝑥}$, and $𝒟$ respectively denote the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, the smallest value that can be assigned to the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, the largest value that can be assigned to the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, and the union of the domains of the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. Clearly, the maximum number of changes (i.e., the number of times the constraint $\left(\right|{\mathrm{𝚅𝙰𝚁}}_i-{\mathrm{𝚅𝙰𝚁}}_{i+1}\left|\right)>\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}$ $(1\le i<n)$ holds) cannot exceed the quantity $m=min(n-1,\overline{\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴}})$. The $(m+1)·\left|𝒟\right|+2$ states of the automaton that only accepts all the solutions to the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint are defined in the following way:

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

• We have $m·\left|𝒟\right|$ intermediate states labelled by $s_{ij}$ $(i\in 𝒟,j\in [0,m\left]\right)$. The first subscript $i$ of state $s_{ij}$ corresponds to the value currently encountered. The second subscript $j$ denotes the number of already encountered satisfied constraints of the form $\left(\right|{\mathrm{𝚅𝙰𝚁}}_k-{\mathrm{𝚅𝙰𝚁}}_{k+1}\left|\right)>\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}$ from the initial state $s_I$ to the state $s_{ij}$.

• We have an accepting state labelled by $s_F$.

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

1. There is a transition, labelled by $i$ from the initial state $s_I$ to the state $s_{i0}$, $(i\in 𝒟)$.

2. There is a transition, labelled by $j$, from every state $s_{ij}$, $(i\in 𝒟,j\in [0,m\left]\right)$, to the accepting state $s_F$.

3. $\forall i\in 𝒟,\forall j\in [0,m],\forall k\in 𝒟\cap [max(\mathrm{𝑚𝑖𝑛},i-\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}),min(\mathrm{𝑚𝑎𝑥},i+\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}\left)\right]$ there is a transition labelled by $k$ from $s_{ij}$ to $s_{kj}$ (i.e., the counter $j$ does not change for values $k$ that are too closed from value $i$).

4. $\forall i\in 𝒟,\forall j\in [0,m-1],\forall k\in 𝒟\setminus [max(\mathrm{𝑚𝑖𝑛},i-\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}),min(\mathrm{𝑚𝑎𝑥},i+\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}\left)\right]$ there is a transition labelled by $k$ from $s_{ij}$ to $s_{kj+1}$ (i.e., the counter $j$ is incremented by $+1$ for values $k$ that are too far from $i$).

We have $\left|𝒟\right|$ transitions of type 1, $\left|𝒟\right|·(m+1)$ transitions of type 2, and at least ${\left|𝒟\right|}^2·m$ transitions of types 3 and 4. Since the maximum value of $m$ is equal to $n-1$, in the worst case we have at least ${\left|𝒟\right|}^2·(n-1)$ transitions. This leads to a worst case time complexity of $O\left(\right|𝒟{|}^2·n^2)$ if we use Pesant's algorithm for filtering the $\mathrm{𝚛𝚎𝚐𝚞𝚕𝚊𝚛}$ constraint [Pesant04].

Figure 5.355.4 depicts the corresponding 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 4, and (3) $\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}$ is equal to 1.

Figure 5.355.4. Counter free non deterministic automaton of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$$(\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴},1,\langle {\mathrm{𝚅𝙰𝚁}}_1,{\mathrm{𝚅𝙰𝚁}}_2,{\mathrm{𝚅𝙰𝚁}}_3,{\mathrm{𝚅𝙰𝚁}}_4\rangle )$ constraint assuming ${\mathrm{𝚅𝙰𝚁}}_i\in [0,3]$ $(1\le i\le 3)$, with initial state $s_I$ and accepting state $s_F$