### 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 $\mathrm{ctr}\left(\mathrm{\pi \pi \pi },{r}_{1},\beta ―,{r}_{n}\right)$ and ${\mathrm{ctr}}^{\text{'}}\left(\mathrm{\pi \pi \pi },{r}_{1},\beta ―,{r}_{n}\right)$ for which, in both cases, the argument $\mathrm{\pi \pi \pi }$ is a collection of items that functionally determines all the other arguments ${r}_{1},\beta ―,{r}_{n}$.

The constraint ${\mathrm{ctr}}^{\text{'}}$ is the reverse constraint of constraint $\mathrm{ctr}$ if, for any collection of items $\mathrm{\pi \pi \pi }$, we have the equivalence $\mathrm{ctr}\left(\mathrm{\pi \pi \pi },{r}_{1},\beta ―,{r}_{n}\right)\beta {\mathrm{ctr}}^{\text{'}}\left({\mathrm{\pi \pi \pi }}^{\mathrm{\pi \pi \pi £}},{r}_{1},\beta ―,{r}_{n}\right)$, where ${\mathrm{\pi \pi \pi }}^{\mathrm{\pi \pi \pi £}}$ denotes the collection $\mathrm{\pi \pi \pi }$ where the items of the collection are reversed. When constraints $\mathrm{ctr}$ and ${\mathrm{ctr}}^{\text{'}}$ are identical we say that constraint $\mathrm{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 $\mathrm{Ο΅}$ 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.