Comptes Rendus
no. 2
Combinatorics/Computer Science
Invertible substitutions on a three-letter alphabet
[Substitutions inversibles sur un alphabet de trois lettres]

Présenté par : Jean-Pierre Kahane

Bo Tan1 ; Zhi-Xiong Wen1 ; Yiping Zhang1
1 Department of Mathematics, Wuhan University, 430072 Wuhan, Hubei, PR China
Comptes Rendus. Mathématique, Volume 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⩽j⩽k. 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⩽j⩽k. 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
Bo Tan 1 ; Zhi-Xiong Wen 1 ; Yiping Zhang 1

1 Department of Mathematics, Wuhan University, 430072 Wuhan, Hubei, PR China 
@article{CRMATH_2003__336_2_111_0,
     author = {Bo Tan and Zhi-Xiong Wen and Yiping Zhang},
     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},
}
TY  - JOUR
AU  - Bo Tan
AU  - Zhi-Xiong Wen
AU  - Yiping Zhang
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
DO  - 10.1016/S1631-073X(02)00006-7
LA  - en
ID  - CRMATH_2003__336_2_111_0
ER  - 
%0 Journal Article
%A Bo Tan
%A Zhi-Xiong Wen
%A Yiping Zhang
%T Invertible substitutions on a three-letter alphabet
%J Comptes Rendus. Mathématique
%D 2003
%P 111-116
%V 336
%N 2
%I Elsevier
%R 10.1016/S1631-073X(02)00006-7
%G en
%F CRMATH_2003__336_2_111_0
Bo Tan; Zhi-Xiong Wen; Yiping Zhang. Invertible substitutions on a three-letter alphabet. Comptes Rendus. Mathématique, Volume 336 (2003) no. 2, pp. 111-116. doi : 10.1016/S1631-073X(02)00006-7. https://comptes-rendus.academie-sciences.fr/mathematique/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] P. Arnoux; S. Ito 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] J. Berstel Recent results in Sturmian words, Developments in Language Theory, II (Magdeburg, 1995), World Sci. Publishing, River Edge, NJ, 1996, pp. 13-24

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

[5] H. Ei; S. Ito 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] R.C. Lyndon; P.E. Schupp Combinatorial Group Theory, Spring-Verlag, Berlin, 1977

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

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

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

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

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

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

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

[15] Z.X. Wen; Y. Zhang 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.

Commentaires - Politique

Ces articles pourraient vous intéresser

Invertible substitutions and local isomorphisms

Zhi-Xiong Wen; Zhi-Ying Wen; Jun Wu

C. R. Math (2002)

On the triplex substitution – combinatorial properties

Bo Tan; Zhi-Xiong Wen; Yiping Zhang

C. R. Math (2008)

On invertible substitutions with two fixed points

Zhi-Xiong Wen; Zhi-Ying Wen; Jun Wu

C. R. Math (2002)