3.7.109. Glue matrix

A reversible constraint for which the catalogue provides an automaton with counters and a glue matrix. A glue matrix is indexed by the states of the automaton associated with the considered constraint as well as by the states of the automaton associated with the reverse of the considered constraint. In the following we assume that the signature constraint involves a consecutive variables of the sequence of variables of the reversible constraint (the signature constraint encodes the mapping of the sequence of variables of the constraint to symbols of the alphabet of the automaton). We consider a sequence of variables and a prefix and suffix of this sequence such that the prefix and suffix have a-1 variables in common. Let q β†’ (resp.Β q ←) be the state of the automaton associated with the constraint (resp.Β the reverse constraint) upon reading the prefix (resp.Β the reverse of the suffix). The entry of the glue matrix corresponding to the state pair (q β†’,q ←) provides a function for computing the result associated with the sequence from the counters values associated with the prefix and the reverse suffix.

As an example consider the πš™πšŽπšŠπš”(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚), which holds if 𝙽 is equal to the number of peaks of the sequence of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. A peak corresponds to an increase between consecutive variables followed by a decrease between consecutive variables. FigureΒ 3.7.32 gives the corresponding automaton that returns the number of peak of a sequence where, to each pair of consecutive variables (πš…π™°πš i ,πš…π™°πš i+1 ) corresponds a signature variable S i passed to the automaton. The following signature constraint links πš…π™°πš i , πš…π™°πš i+1 and S i : (πš…π™°πš i <πš…π™°πš i+1 ⇔S i =0) ∧ (πš…π™°πš i =πš…π™°πš i+1 ⇔S i =1) ∧ (πš…π™°πš i >πš…π™°πš i+1 ⇔S i =2).

Figure 3.7.32. Automaton of the πš™πšŽπšŠπš” constraint and its glue matrix

FigureΒ 3.7.33 illustrates the use of the glue matrix of the πš™πšŽπšŠπš” constraint on the sequence 1,1,4,8,6,2,7,1 decomposed in a prefix 1,1,4,8 and a suffix 8,6,2,7,1 that overlap by one position, one position since the arity of the signature constraint is equal to two. Since the automaton of the πš™πšŽπšŠπš” constraint ends up in state u when applied to the prefix and to the reverse suffix we use the lower rightmost entry of the glue matrix to link the total number of peaks of the sequence 1,1,4,8,6,2,7,1 with the number of peaks of the prefix 1,1,4,8 and the suffix 8,6,2,7,1.

Figure 3.7.33. Illustrating the use of the state pair (u,u) of the glue matrix for linking 𝙽 with the counters variables obtained after reading the prefix 1,1,4,8 and corresponding suffix 8,6,2,7,1 of the sequence 1,1,4,8,6,2,7,1; note that the suffix 8,6,2,7,1 (in pink) is proceed in reverse order; the left (resp.Β right) table shows the initialisation (for i=0) and the evolution (for i>0) of the state of the automaton and of its counter C upon reading the prefix 1,1,4,8 (resp.Β the suffix 1,7,2,6,8).