×

Local isomorphisms of invertible substitutions. (English. Abridged French version) Zbl 0812.11018

It is known that the group of automorphisms of the free group over two generators \(a\), \(b\) is generated by the elements \(\alpha\), \(\beta\), \(\gamma\), where \(\alpha(a)= b\), \(\alpha(b)=a\), \(\beta(a)= ab\), \(\beta(b)=b\), \(\gamma(a)= ba\), \(\gamma(b)=b\) (result proved by Nielsen).
The authors consider the monoid of invertible morphisms of the free monoid over two letters (a morphism is said to be invertible if its natural extension to the free group over two symbols is an automorphism). They show the remarkable result that this monoid is generated (as a monoid) by the same elements \(\alpha\), \(\beta\), \(\gamma\). They also give a necessary and sufficient condition for the fixed points of two invertible morphisms to be locally isomorphic (i.e. such that every factor of one of them is either a factor of the other one or the mirror image of a factor of the other one).
Note that this work is related to previous works of J. Peyrière and the authors [Enseign. Math., II. Sér. 39, 153-175 (1993; Zbl 0798.20017)] and a paper of the reviewer and J. Peyrière [C. R. Acad. Sci., Paris, II. Sér. 302, 1135-1136 (1986; Zbl 0587.65033)]. Note also that this paper together with a paper of F. Mignosi and P. Séébold [J. Théor. Nombres Bordx. 5, 221-233 (1993; Zbl 0797.11029)] shows that a morphism of the free monoid over two symbols is invertible if and only if it is Sturmian.

MSC:

11B85 Automata sequences
68R15 Combinatorics on words
20M05 Free semigroups, generators and relations, word problems
08A35 Automorphisms and endomorphisms of algebraic structures
PDFBibTeX XMLCite