Combinatorics/Computer Science
Invertible substitutions on a three-letter alphabet
[Substitutions inversibles sur un alphabet de trois lettres]
Comptes Rendus. Mathématique, Tome 336 (2003) no. 2, pp. 111-116.

Nous étudions la structure des substitutions inversibles sur un alphabet à trois lettres. Nous prouvons qu'il existe un ensemble fini 𝕊 de substitutions inversibles tel que toute substitution inversible puisse être écrite comme Iwσ1σ2∘⋯∘σk, où Iw est l'automorphisme intérieur associé à w et où σ j 𝕊 pour 1⩽jk. Comme conséquence, M est la matrice d'une substitution inversible si et seulement si elle est un produit fini de matrices élémentaires non-négatives.

We study the structure of invertible substitutions on a three-letter alphabet. We show that there exists a finite set 𝕊 of invertible substitutions such that any invertible substitution can be written as Iwσ1σ2∘⋯∘σk, where Iw is the inner automorphism associated with w, and σ j 𝕊 for 1⩽jk. As a consequence, M is the matrix of an invertible substitution if and only if it is a finite product of non-negative elementary matrices.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(02)00006-7
Tan, Bo 1 ; Wen, Zhi-Xiong 1 ; Zhang, Yiping 1

1 Department of Mathematics, Wuhan University, 430072 Wuhan, Hubei, PR China
@article{CRMATH_2003__336_2_111_0,
     author = {Tan, Bo and Wen, Zhi-Xiong and Zhang, Yiping},
     title = {Invertible substitutions on a three-letter alphabet},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {111--116},
     publisher = {Elsevier},
     volume = {336},
     number = {2},
     year = {2003},
     doi = {10.1016/S1631-073X(02)00006-7},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/S1631-073X(02)00006-7/}
}
TY  - JOUR
AU  - Tan, Bo
AU  - Wen, Zhi-Xiong
AU  - Zhang, Yiping
TI  - Invertible substitutions on a three-letter alphabet
JO  - Comptes Rendus. Mathématique
PY  - 2003
SP  - 111
EP  - 116
VL  - 336
IS  - 2
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/S1631-073X(02)00006-7/
DO  - 10.1016/S1631-073X(02)00006-7
LA  - en
ID  - CRMATH_2003__336_2_111_0
ER  - 
%0 Journal Article
%A Tan, Bo
%A Wen, Zhi-Xiong
%A Zhang, Yiping
%T Invertible substitutions on a three-letter alphabet
%J Comptes Rendus. Mathématique
%D 2003
%P 111-116
%V 336
%N 2
%I Elsevier
%U http://www.numdam.org/articles/10.1016/S1631-073X(02)00006-7/
%R 10.1016/S1631-073X(02)00006-7
%G en
%F CRMATH_2003__336_2_111_0
Tan, Bo; Wen, Zhi-Xiong; Zhang, Yiping. Invertible substitutions on a three-letter alphabet. Comptes Rendus. Mathématique, Tome 336 (2003) no. 2, pp. 111-116. doi : 10.1016/S1631-073X(02)00006-7. http://www.numdam.org/articles/10.1016/S1631-073X(02)00006-7/

[1] P. Arnoux et al., Introduction to finite automata and substitution dynamical systems, in: Lecture Notes in Math., Springer-Verlag, to appear

[2] Arnoux, P.; Ito, S. Pisot substitutions and Rauzy fractals, Journées Montoises d'Informatique Théorique (Marne-la-Vallée, 2000) (Bull. Belgian Math. Soc. Simon Stevin), Volume 8 (2001) no. 2, pp. 181-207

[3] Berstel, J. Recent results in Sturmian words, Developments in Language Theory, II (Magdeburg, 1995), World Sci. Publishing, River Edge, NJ, 1996, pp. 13-24

[4] Cobham, A. Uniform tag sequences, Math. System Theory, Volume 6 (1972), pp. 164-192

[5] Ei, H.; Ito, S. Decomposition theorem for invertible substitution, Osaka J. Math., Volume 34 (1998), pp. 821-834

[6] M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, 2002, to appear. Available at http://www-igm.univ-mlv.fr/~berstel/Lothaire

[7] Lyndon, R.C.; Schupp, P.E. Combinatorial Group Theory, Spring-Verlag, Berlin, 1977

[8] Magnus, W.; Karrass, A.; Solitar, D. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations, Dover, 1976

[9] Nielsen, J. Die Isomorphismen der freien Gruppen, Math. Ann., Volume 91 (1924), pp. 169-209

[10] Peyrière, J.; Wen, Z.-X.; Wen, Z.-Y. Polynomês associées aux endomorphismes de groupes libres, Enseign. Math., Volume 39 (1993), pp. 153-175

[11] Séébold, P. Fibonacci morphisms and Sturmian words, Theoret. Comput. Sci., Volume 88 (1991), pp. 365-384

[12] Wen, Z.-X.; Wen, Z.-Y. Local isomorphism of the invertible substitutions, C. R. Acad. Sci. Paris Sér. I Math., Volume 318 (1994), pp. 299-304

[13] Wen, Z.-X.; Wen, Z.-Y. Some properties of the singular words of the Fibonacci word, European J. Combin., Volume 15 (1994), pp. 587-598

[14] Wen, Z.-X.; Wen, Z.-Y.; Wu, J. Invertible substitutions and local isomorphisms, C. R. Acad. Sci. Paris Sér. I Math., Volume 334 (2002), pp. 629-634

[15] Wen, Z.X.; Zhang, Y. Some remarks on invertible substitutions on three letter alphabet, Chinese Sci. Bull., Volume 44 (1999) no. 19, pp. 1755-1760

Cité par Sources :

Research supported by NSFC and by the Special Funds for Major State Basic Research Projects of China.