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 (1≀i≀n) 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 π’œ ' 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 (1≀i≀n) 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 πš–πš’πš—πš’πš–πšžπš– constraint and of its open counterpart, the πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš– constraint.

Figure 3.7.36. (Constructing the (B)Β automaton of the πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš– constraint from the (A)Β automaton of the πš–πš’πš—πš’πš–πšžπš– constraint
ctrs/open_automaton_constraint