On the triplex substitution – combinatorial properties

Bo Tan; Zhi-Xiong Wen; Yiping Zhang

doi:10.1016/j.crma.2008.06.013

Combinatorics

On the triplex substitution – combinatorial properties
[Sur la substitution triplexe – propriétés combinatoires]

Présenté par : Jean-Pierre Kahane

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

¹ Department of Mathematics, Huazhong University of Science and Technology, Wuhan 430074, PR China
² Department of Mathematics, Wuhan University, Wuhan 430072, PR China

Comptes Rendus. Mathématique, Volume 346 (2008) no. 15-16, pp. 813-818.

Abstract (VO)
Résumé

If a substitution τ over a three-letter alphabet has a positively linear complexity, that is, $P_{τ} (n) = C_{1} n + C_{2}$ ( $n ⩾ 1$ ) with $C_{1}, C_{2} ⩾ 0$ , there are only 4 possibilities: $P_{τ} (n) = 3$ , $n + 2$ , $2 n + 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 \mapsto a b$ , $b \mapsto a c b$ , $c \mapsto a c c$ . 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.

Si une substitution τ sur un alphabet de trois lettres a une complexité positivement linéaire, c'est-à-dire $P_{τ} (n) = C_{1} n + C_{2}$ ( $n ⩾ 1$ ) où $C_{1}, C_{2} ⩾ 0$ , alors il n'y a que quatre possibilités : $P_{τ} (n) = 3$ , $n + 2$ , $2 n + 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 \mapsto a b$ , $b \mapsto a c b$ , $c \mapsto a c c$ . 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.

Reçu le : 2008-02-18
Accepté le : 2008-06-18
Publié le : 2008-07-24

DOI : 10.1016/j.crma.2008.06.013

Affiliations des auteurs :

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

¹ Department of Mathematics, Huazhong University of Science and Technology, Wuhan 430074, PR China
² 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/

Bibliographie
Cité par

[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é $2 n + 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

Bo Tan; Zhixiong Wen; Yiping Zhang On the triplex substitution – Rauzy fractal, Comptes Rendus. Mathématique. Académie des Sciences, Paris, Volume 346 (2008) no. 17-18, pp. 925-930 | DOI:10.1016/j.crma.2008.06.014 | Zbl:1213.68481

Cité par 1 document. Sources : zbMATH

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

Commentaires - Politique

Il n'y a aucun commentaire pour cet article. Soyez le premier à écrire un commentaire !

Publier un nouveau commentaire:

Publier une nouvelle réponse: