Invertible substitutions and Sturmian sequences. (Q1414634): Difference between revisions

A morphism of the free monoid on two letters \(a\) and \(b\) (also called binary substitution) is invertible if its natural extension to the free group generated by \(\{a,b\}\) is invertible. A morphism of the free monoid generated by \(\{a,b\}\) is called Sturmian if there exists a Sturmian sequence whose image is Sturmian (equivalently if all Sturmian sequences have Sturmian images). Actually the set of invertible morphisms and the set of Sturmian morphisms above are equal: both are equal to the monoid generated by three particular morphisms [see \textit{Zhixiong Wen} and \textit{Zhiying Wen}, C. R. Acad. Sci., Paris, Sér. I 318, 299--304 (1994; Zbl 0812.11018)] and \textit{F. Mignosi} and \textit{P. Séébold}, J. Théor. Nombres Bordx. 5, 221--233 (1993; Zbl 0797.11029)]. In the paper under review the authors give a new characterization of invertible binary morphisms: the morphism \(\tau\) is invertible if and only if there exist two words \(u\) and \(v\) on the alphabet \(\{a,b\}\) such that either \[ \begin{cases} \tau(ab)= uabv\\ \tau(ba)= ubav\end{cases}\qquad\text{or}\qquad \begin{cases} \tau(ab)= ubav\\ \tau(ba)= uabv.\end{cases} \] The paper ends with properties of fixed points of invertible morphisms. Note that References 6 and 30 have appeared [see \textit{W.-T. Cao} and \textit{Z.-Y. Wen}, Theor. Comput. Sci. 304, 365--385 (2003; Zbl 1045.68109) and \textit{Z. Wen}, \textit{Z. Wen} and \textit{J. Wu}, C. R., Math., Acad. Sci. Paris 334, 727--731 (2002; Zbl 0996.68149)]. Also note that the second book of Lothaire cited in the paper is not a new version of the first one but a continuation [see \textit{M. Lothaire}, Algebraic combinatorics on words, Cambridge University Press, Cambridge (2002; Zbl 1001.68093)].