In this paper we study bi-infinite words on two letters. We say that such a word has stiffness if the number of different subwords of length equals for all sufficiently large. The word is called -balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most . In the present paper we give a complete description of the class of bi-infinite words of stiffness and show that the number of subwords of length from this class has growth order . In the case we give an exact formula. We also consider the class of -balanced bi-infinite words. It is well-known that the number of subwords of length from this class has growth order if . In contrast, we show that the number is when .
Dans cet article on étudie des mots bi-infinis sur deux symboles. On dit qu’un tel mot est de rigidité si le nombre de facteurs différents de longueur est égal à pour grand. Un tel mot est appelé -balancé si le nombre d’occurrences du symbole dans deux facteurs quelconques de même longueur peuvent différer au plus de . Dans cet article on donne une description complète de la classe des mots bi-infinis de rigidité et on montre que le nombre de facteurs de longueur de cette classe est de l’ordre de . Dans le cas on donne une formule exacte. On considère aussi la classe des mots bi-infinis -balancés. Il est bien connu que le nombre de facteurs de longueur est de l’ordre de si . En revanche, on montre que ce nombre est si .
@article{JTNB_2001__13_2_421_0, author = {Heinis, Alex}, title = {On low-complexity bi-infinite words and their factors}, journal = {Journal de th\'eorie des nombres de Bordeaux}, pages = {421--442}, publisher = {Universit\'e Bordeaux I}, volume = {13}, number = {2}, year = {2001}, mrnumber = {1879667}, zbl = {1013.68155}, language = {en}, url = {http://archive.numdam.org/item/JTNB_2001__13_2_421_0/} }
TY - JOUR AU - Heinis, Alex TI - On low-complexity bi-infinite words and their factors JO - Journal de théorie des nombres de Bordeaux PY - 2001 SP - 421 EP - 442 VL - 13 IS - 2 PB - Université Bordeaux I UR - http://archive.numdam.org/item/JTNB_2001__13_2_421_0/ LA - en ID - JTNB_2001__13_2_421_0 ER -
Heinis, Alex. On low-complexity bi-infinite words and their factors. Journal de théorie des nombres de Bordeaux, Volume 13 (2001) no. 2, pp. 421-442. http://archive.numdam.org/item/JTNB_2001__13_2_421_0/
[A] Codages de rotations et de basses complexités. Thèse de Doctorat, Université d'Aix-Marseille II, 1996.
,[A/R] Réprésentation géométrique des suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991), 199-215. | Numdam | MR | Zbl
, ,[B/dL] Sturmian words, Lyndon words and trees. Theoret. Comput. Sc. 178 (1993), 171-203. | MR | Zbl
, ,[B/P] Theory of Codes. Academic Press, 1985. | MR | Zbl
, ,[B/Po] A geometric proof of the enumeration formula for Sturmian words. J. Algebra Comput. 3 (1993), 349-355. | MR | Zbl
, ,[Bo/L] Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux 5 (1993), 23-51. | Numdam | MR | Zbl
, ,[Br] Descriptions of the characteristic sequence of an arrational. Canad. Math. Bull. 36 (1993), 15-21. | MR | Zbl
,[C] Sequences with minimal block growth II. Math. Systems Th. 8 (1975), 376-382. | MR | Zbl
,[C/H] Sequences with minimal block growth. Math. Systems Th. 7 (1971), 138-153. | MR | Zbl
, ,[D] Caractérisation des N -écritures et application à l'étude des suites de complexité n + cste. Theoret. Comput. Sc. 215 (1999), 31-49. | MR | Zbl
,[D/GB] Sur les facteurs des suites de Sturm. Theoret. Comput. Sc. 71 (1990), 381-400. | MR | Zbl
, ,[H/W] An Introduction to the Theory of Numbers. Oxford Univ. Press, Third Edition, 1954. | MR | Zbl
, ,[H/T] Extending balanced and stiff words. Report no. W97-15, University of Leiden, 1997.
, ,[dL/Mi] Some combinatorial properties of Sturmian words. Theoret. Comput. Sc. 136 (1994), 361-385. | MR | Zbl
, ,[H/H] Symbolic dynamics II - Sturmian trajectories. Amer. J. Math. 62 (1940), 1-42. | JFM | MR | Zbl
, ,[Mi] On the number of factors of Sturmian words. Theoret. Comput. Sc. 82 (1991), 71-84. | MR | Zbl
,(Mi/S] Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993), 211-233. | Numdam | MR | Zbl
, ,[P] Minimal symbolic flows having minimal block growth. Math. Systems Th. 8 (1975), 309-315. | MR | Zbl
,[S] Beatty sequences, continued fractions and certain shift operators. Canad. Math. Bull. 19 (1976), 473-482. | MR | Zbl
,[T] Intertwinings of periodic sequences. Indag. Math. 9 (1998), 113-122. | MR | Zbl
,