Heinis, Alex
On low-complexity bi-infinite words and their factors
Journal de théorie des nombres de Bordeaux, Tome 13 (2001) no. 2 , p. 421-442
Zbl 1013.68155 | MR 1879667
URL stable : http://www.numdam.org/item?id=JTNB_2001__13_2_421_0

Dans cet article on étudie des mots bi-infinis sur deux symboles. On dit qu’un tel mot est de rigidité k si le nombre de facteurs différents de longueur n est égal à n+k pour n grand. Un tel mot est appelé k-balancé si le nombre d’occurrences du symbole a dans deux facteurs quelconques de même longueur peuvent différer au plus de k. Dans cet article on donne une description complète de la classe des mots bi-infinis de rigidité k et on montre que le nombre de facteurs de longueur n de cette classe est de l’ordre de n 3 . Dans le cas k=1 on donne une formule exacte. On considère aussi la classe des mots bi-infinis k-balancés. Il est bien connu que le nombre de facteurs de longueur n est de l’ordre de n 3 si k=1. En revanche, on montre que ce nombre est 2 n/2 si k2.
In this paper we study bi-infinite words on two letters. We say that such a word has stiffness k if the number of different subwords of length n equals n+k for all n sufficiently large. The word is called k-balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most k. In the present paper we give a complete description of the class of bi-infinite words of stiffness k and show that the number of subwords of length n from this class has growth order n 3 . In the case k=1 we give an exact formula. We also consider the class of k-balanced bi-infinite words. It is well-known that the number of subwords of length n from this class has growth order n 3 if k=1. In contrast, we show that the number is 2 n/2 when k2.

Bibliographie

[A] P. Alessandri, Codages de rotations et de basses complexités. Thèse de Doctorat, Université d'Aix-Marseille II, 1996.

[A/R] P. Arnoux, G. Rauzy, Réprésentation géométrique des suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991), 199-215. Numdam | MR 1116845 | Zbl 0789.28011

[B/dL] J. Berstel, A. De Luca, Sturmian words, Lyndon words and trees. Theoret. Comput. Sc. 178 (1993), 171-203. MR 1453849 | Zbl 0901.68155

[B/P] J. Berstel, D. Perrin, Theory of Codes. Academic Press, 1985. MR 797069 | Zbl 0587.68066

[B/Po] J. Berstel, M. Pocchiola, A geometric proof of the enumeration formula for Sturmian words. J. Algebra Comput. 3 (1993), 349-355. MR 1240390 | Zbl 0802.68099

[Bo/L] J.-P. Borel, F. Laubie, Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux 5 (1993), 23-51. Numdam | MR 1251226 | Zbl 0839.11008

[Br] T.C. Brown, Descriptions of the characteristic sequence of an arrational. Canad. Math. Bull. 36 (1993), 15-21. MR 1205889 | Zbl 0804.11021

[C] E.M. Coven, Sequences with minimal block growth II. Math. Systems Th. 8 (1975), 376-382. MR 391053 | Zbl 0299.54032

[C/H] E.M. Coven, G.A. Hedlund, Sequences with minimal block growth. Math. Systems Th. 7 (1971), 138-153. MR 322838 | Zbl 0256.54028

[D] G. Didier, Caractérisation des N -écritures et application à l'étude des suites de complexité n + cste. Theoret. Comput. Sc. 215 (1999), 31-49. MR 1678793 | Zbl 0913.68163

[D/GB] S. Dulucq, D. Gouyou-Beauchamps, Sur les facteurs des suites de Sturm. Theoret. Comput. Sc. 71 (1990), 381-400. MR 1057771 | Zbl 0694.68048

[H/W] G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers. Oxford Univ. Press, Third Edition, 1954. MR 67125 | Zbl 0058.03301

[H/T] A. Heinis, R. Tijdeman, Extending balanced and stiff words. Report no. W97-15, University of Leiden, 1997.

[dL/Mi] A. De Luca, F. Mignosi, Some combinatorial properties of Sturmian words. Theoret. Comput. Sc. 136 (1994), 361-385. MR 1311214 | Zbl 0874.68245

[H/H] M. Morse, G.A. Hedlund, Symbolic dynamics II - Sturmian trajectories. Amer. J. Math. 62 (1940), 1-42. JFM 66.0188.03 | MR 745 | Zbl 0022.34003

[Mi] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sc. 82 (1991), 71-84. MR 1112109 | Zbl 0728.68093

(Mi/S] F. Mignosi, P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993), 211-233. Numdam | MR 1265903 | Zbl 0797.11029

[P] M.E. Paul, Minimal symbolic flows having minimal block growth. Math. Systems Th. 8 (1975), 309-315. MR 380760 | Zbl 0306.54056

[S] K.B. Stolarsky, Beatty sequences, continued fractions and certain shift operators. Canad. Math. Bull. 19 (1976), 473-482. MR 444558 | Zbl 0359.10028

[T] R. Tijdeman, Intertwinings of periodic sequences. Indag. Math. 9 (1998), 113-122. MR 1618219 | Zbl 0918.11012