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

Présenté par : Jean-Pierre Kahane

Tan, Bo1 ; Wen, Zhi-Xiong1 ; Zhang, Yiping2
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, Tome 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
Tan, Bo 1 ; Wen, Zhi-Xiong 1 ; Zhang, Yiping 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 = {Tan, Bo and Wen, Zhi-Xiong and Zhang, Yiping},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2008.06.013/}
}
TY  - JOUR
AU  - Tan, Bo
AU  - Wen, Zhi-Xiong
AU  - Zhang, Yiping
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2008.06.013/
DO  - 10.1016/j.crma.2008.06.013
LA  - en
ID  - CRMATH_2008__346_15-16_813_0
ER  - 
%0 Journal Article
%A Tan, Bo
%A Wen, Zhi-Xiong
%A Zhang, Yiping
%T On the triplex substitution – combinatorial properties
%J Comptes Rendus. Mathématique
%D 2008
%P 813-818
%V 346
%N 15-16
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2008.06.013/
%R 10.1016/j.crma.2008.06.013
%G en
%F CRMATH_2008__346_15-16_813_0
Tan, Bo; Wen, Zhi-Xiong; Zhang, Yiping. On the triplex substitution – combinatorial properties. Comptes Rendus. Mathématique, Tome 346 (2008) no. 15-16, pp. 813-818. doi : 10.1016/j.crma.2008.06.013. http://www.numdam.org/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] Allouche, J.-P. Automates finis en théorie des nombres, Exposition. Math., Volume 5 (1987), pp. 239-266

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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