×

Decomposition theorem on invertible substitutions. (English) Zbl 0924.20040

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. Z. Wen and 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 [F. Mignosi and 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 [J. Berstel and P. Séébold, Bull. Belg. Math. Soc. – Simon Stevin 1, No. 2, 175-189 (1994; Zbl 0803.68095)].

MSC:

20M05 Free semigroups, generators and relations, word problems
68R15 Combinatorics on words
11B85 Automata sequences
20E05 Free nonabelian groups
20E36 Automorphisms of infinite groups
PDFBibTeX XMLCite