Invertible substitutions on a three-letter alphabet

Bo Tan; Zhi-Xiong Wen; Yiping Zhang

doi:10.1016/S1631-073X(02)00006-7

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 Tan ¹ ; Zhi-Xiong Wen ¹ ; Yiping Zhang ¹

¹ Department of Mathematics, Wuhan University, 430072 Wuhan, Hubei, PR China

Comptes Rendus. Mathématique, Volume 336 (2003) no. 2, pp. 111-116.

Résumé
Abstract

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 I_w∘σ₁∘σ₂∘⋯∘σ_k, où I_w est l'automorphisme intérieur associé à w et où $σ_{j} \in 𝕊$ 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 I_w∘σ₁∘σ₂∘⋯∘σ_k, where I_w is the inner automorphism associated with w, and $σ_{j} \in 𝕊$ 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 : 2002-10-29
Accepté le : 2002-11-05
Publié le : 2003-01-15

DOI : 10.1016/S1631-073X(02)00006-7

Affiliations des auteurs :

Bo Tan ¹ ; Zhi-Xiong Wen ¹ ; Yiping Zhang ¹

¹ 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/

Bibliographie
Cité par

[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