3.7.214. Reverse of a constraint

A constraint which has a reverse constraint, where the reverse is defined in the following way. Consider two constraints ctr (π‘π‘œπ‘™,r 1 ,β‹―,r n ) and ctr ' (π‘π‘œπ‘™,r 1 ,β‹―,r n ) for which, in both cases, the argument π‘π‘œπ‘™ is a collection of items that functionally determines all the other arguments r 1 ,β‹―,r n .

The constraint ctr ' is the reverse constraint of constraint ctr if, for any collection of items π‘π‘œπ‘™, we have the equivalence ctr (π‘π‘œπ‘™,r 1 ,β‹―,r n )⇔ ctr ' (π‘π‘œπ‘™ π‘Ÿπ‘’π‘£ ,r 1 ,β‹―,r n ), where π‘π‘œπ‘™ π‘Ÿπ‘’π‘£ denotes the collection π‘π‘œπ‘™ where the items of the collection are reversed. When constraints ctr and ctr ' are identical we say that constraint ctr is its own reverse.

The previous enumeration provides the list of reversible constraints where, for each reversible constraint, we give its reverse only when it is different from the original constraint.

Note that if a constraint can be represented by a counter deterministic automaton with one single counter that is only incremented and for which all states are accepting, then by computing the reverse automaton, the corresponding reverse constraint can be mechanically obtained. However note that the reverse automaton may be non-deterministic and may contain Ο΅ transitionsΒ [Mohri2009]. FigureΒ 3.7.57 gives an automaton counting the number of occurrences of words 001 in a sequence and its reverse automaton. FigureΒ 3.7.58 provides an automaton with one counter and its reverse automaton that has a different number of states.

Figure 3.7.57. (A)Β Counter automaton returning the number of occurrences 𝙽 of word 001 in a sequence, and (B)Β its reverse counter automaton (returning the number of occurrences 𝙽 of word 100 in a sequence)
ctrs/preface-198-tikz
Figure 3.7.58. (A)Β Counter automaton, and (B) its reverse counter automaton which has a different number of states
ctrs/preface-199-tikz