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\beta €i\beta €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 $\mathrm{\pi }$ for which we already have a finite deterministic automaton $\mathrm{\pi }$ that only accepts the set of solutions of $\mathrm{\pi }$. Constructing the finite deterministic automaton ${\mathrm{\pi }}^{\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 $\mathrm{\pi }$. First, to each transition of $\mathrm{\pi }$ we add the fact that the corresponding Boolean variable must also be equal to 1. Second, to each state of $\mathrm{\pi }$ we add a loop transition for which the corresponding Boolean variable ${B}_{i}$ $\left(1\beta €i\beta €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{\pi \pi \pi \pi \pi \pi \pi }$ constraint and of its open counterpart, the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint.