3.7.164. Open automaton constraint

A constraint for which the set of solutions can be recognised by a so called open automaton. An open automaton is a finite deterministic automaton taking as input a sequence of variables ${V}_{1}{V}_{2}...{V}_{n}$ as well as a sequence of 0-1 variables ${B}_{1}{B}_{2}...{B}_{n}$. A variable ${B}_{i}$ $\left(1\le i\le n\right)$ set to value 0 means that the corresponding variable ${V}_{i}$ is removed from the sequence of variables ${V}_{1}{V}_{2}...{V}_{n}$.

Consider a constraint $𝒞$ for which we already have a finite deterministic automaton $𝒜$ that only accepts the set of solutions of $𝒞$. Constructing the finite deterministic automaton ${𝒜}^{\text{'}}$ that only recognises the set of solutions of the open version of constraint $C$ can be done in a systematic way from the automaton $𝒜$. First, to each transition of $𝒜$ we add the fact that the corresponding Boolean variable must also be equal to 1. Second, to each state of $𝒜$ we add a loop transition for which the corresponding Boolean variable ${B}_{i}$ $\left(1\le i\le n\right)$ must be equal to 0 (since variable ${V}_{i}$ is ignored, we stay within the same state). Figure 3.7.36 illustrates this construction in the context of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint and of its open counterpart, the $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint.