Comptes Rendus
no. 15-16
Combinatorics
On the triplex substitution – combinatorial properties
[Sur la substitution triplexe – propriétés combinatoires]

Présenté par : Jean-Pierre Kahane

Bo Tan1 ; Zhi-Xiong Wen1 ; Yiping Zhang2
1 Department of Mathematics, Huazhong University of Science and Technology, Wuhan 430074, PR China
2 Department of Mathematics, Wuhan University, Wuhan 430072, PR China
Comptes Rendus. Mathématique, Volume 346 (2008) no. 15-16, pp. 813-818.

Si une substitution τ sur un alphabet de trois lettres a une complexité positivement linéaire, c'est-à-dire Pτ(n)=C1n+C2 (n⩾1) où C1,C2⩾0, alors il n'y a que quatre possibilités : Pτ(n)=3, n+2, 2n+1 ou 3n. Les trois premiers cas ont été étudiés par différents auteurs, mais le cas 3n reste non entièrement élucidé. Nous considérons donc la substitution triplexe σ:a↦ab, b↦acb, c↦acc. Analysant la structure des facteurs de son point fixe nous montrons que sa complexité est 3n. La substitution triplexe est un exemple typique de substitution inversible sur un alphabet de trois lettres.

If a substitution τ over a three-letter alphabet has a positively linear complexity, that is, Pτ(n)=C1n+C2 (n⩾1) with C1,C2⩾0, there are only 4 possibilities: Pτ(n)=3, n+2, 2n+1 or 3n. The first three cases have been studied by many authors, but the case 3n remained unclear. This leads us to consider the triplex substitution σ:a↦ab, b↦acb, c↦acc. Studying the factor structure of its fixed point, which is quite different from the other cases, we show that it is of complexity 3n. We remark that the triplex substitution is also a typical example of invertible substitution over a three-letter alphabet.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2008.06.013
Bo Tan 1 ; Zhi-Xiong Wen 1 ; Yiping Zhang 2

1 Department of Mathematics, Huazhong University of Science and Technology, Wuhan 430074, PR China
2 Department of Mathematics, Wuhan University, Wuhan 430072, PR China 
@article{CRMATH_2008__346_15-16_813_0,
     author = {Bo Tan and Zhi-Xiong Wen and Yiping Zhang},
     title = {On the triplex substitution {\textendash} combinatorial properties},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {813--818},
     publisher = {Elsevier},
     volume = {346},
     number = {15-16},
     year = {2008},
     doi = {10.1016/j.crma.2008.06.013},
     language = {en},
}
TY  - JOUR
AU  - Bo Tan
AU  - Zhi-Xiong Wen
AU  - Yiping Zhang
TI  - On the triplex substitution – combinatorial properties
JO  - Comptes Rendus. Mathématique
PY  - 2008
SP  - 813
EP  - 818
VL  - 346
IS  - 15-16
PB  - Elsevier
DO  - 10.1016/j.crma.2008.06.013
LA  - en
ID  - CRMATH_2008__346_15-16_813_0
ER  - 
%0 Journal Article
%A Bo Tan
%A Zhi-Xiong Wen
%A Yiping Zhang
%T On the triplex substitution – combinatorial properties
%J Comptes Rendus. Mathématique
%D 2008
%P 813-818
%V 346
%N 15-16
%I Elsevier
%R 10.1016/j.crma.2008.06.013
%G en
%F CRMATH_2008__346_15-16_813_0
Bo Tan; Zhi-Xiong Wen; Yiping Zhang. On the triplex substitution – combinatorial properties. Comptes Rendus. Mathématique, Volume 346 (2008) no. 15-16, pp. 813-818. doi : 10.1016/j.crma.2008.06.013. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2008.06.013/

[1] P. Alessandri, Classification et représentation des suites de complexité n+2, Manuscrit non publié, 1995

[2] J.-P. Allouche Automates finis en théorie des nombres, Exposition. Math., Volume 5 (1987), pp. 239-266

[3] P. Arnoux; S. Ito Pisot substitutions and Rauzy fractals, Marne-la-Vallée, 2000 (Bull. Belg. Math. Soc. Simon Stevin), Volume 8 (2001), pp. 181-207

[4] P. Arnoux; G. Rauzy Représentation géométrique de suites de complexité 2n+1, Bull. Soc. Math. France, Volume 119 (1991), pp. 199-215

[5] J. Cassaigne Special factors of sequences with linear subword complexity, Developments in Language Theory II (DLT'95), Magdeburg, Allemagne, World Sci., 1996, pp. 25-34

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

[7] M. Lothaire Combinatorics on Words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley, 1983

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

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

[10] M. Morse; G.A. Hedlund Symbolic dynamics II: Sturmian trajectories, Amer. J. Math., Volume 62 (1940), pp. 1-42

[11] B. Mossé Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, Volume 124 (1996), pp. 329-346

[12] N. Pytheas Fogg Substitutions in dynamics, arithmetics and combinatorics (V. Berthé; S. Ferenczi; C. Mauduit; A. Siegel, eds.), Lecture Notes in Mathematics, vol. 1794, Springer, 2002

[13] G. Rote Sequences with subword complexity 2n, J. Number Theory, Volume 46 (1994), pp. 196-213

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

[15] B. Tan; Z.-X. Wen; Y. Zhang The structure of invertible substitutions on a three-letter alphabet, Adv. Appl. Math., Volume 32 (2004), pp. 736-753

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

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

Cité par Sources :

⁎ Research supported by NSFC No. 10501035, 10631040, 10571140 and 10671150.

Commentaires - Politique

Ces articles pourraient vous intéresser

On the triplex substitution – Rauzy fractal

Bo Tan; Zhi-Xiong Wen; Yiping Zhang

C. R. Math (2008)

Invertible substitutions on a three-letter alphabet

Bo Tan; Zhi-Xiong Wen; Yiping Zhang

C. R. Math (2003)

Invertible substitutions and local isomorphisms

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

C. R. Math (2002)