Decomposition theorem on invertible substitutions
A substitution on \(\{1,2\}\) is exactly a morphism of the free group generated by \(\{1,2\}\) such that the images of 1 and 2 do not contain any symbol \(1^-\) or \(2^-\). A substitution is thus called invertible if it is furthermore an automorphism of this free group. \textit{Z. Wen} and \textit{Z. Wen} proved [C. R. Acad. Sci., Paris, Sér. I 318, No. 4, 299-304 (1994; Zbl 0812.11018)] that the monoid of invertible substitutions is generated by the following three substitutions: \[ \begin{cases} 1\to 2\\ 2\to 1\end{cases}\qquad\begin{cases} 1\to 12\\ 2\to 1\end{cases}\qquad\begin{cases} 1\to 21\\ 2\to 1\end{cases}. \] In the paper under review the authors give a new proof of this result and a geometrical characterization of the invertible substitutions. Note that two other characterizations of the invertible substitutions are known: (1) they are exactly the morphisms that send any (resp. one) Sturmian sequence to a Sturmian sequence [\textit{F. Mignosi} and \textit{P. Séébold}, J. Théor. Nombres Bordx. 5, No. 2, 221-233 (1993; Zbl 0797.11029)]; (2) they are exactly the morphisms \(\varphi\) such that \(\varphi(12)\neq\varphi(21)\) and \(z=\varphi(21121121211212)\) is balanced, i.e., for any two factors (subwords) \(u\) and \(v\) of \(z\) having the same length, the numbers of 1's in \(u\) and \(v\) are either the same or differ by 1 [\textit{J. Berstel} and \textit{P. Séébold}, Bull. Belg. Math. Soc. -- Simon Stevin 1, No. 2, 175-189 (1994; Zbl 0803.68095)].
scientific article; zbMATH DE number 1270291