On low-complexity bi-infinite words and their factors

Alex Heinis

Alex Heinis

Journal de théorie des nombres de Bordeaux, Tome 13 (2001) no. 2, pp. 421-442.

Résumé
Abstract

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 $\geq 2^{n / 2}$ si $k \geq 2$ .

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 $\geq 2^{n / 2}$ when $k \geq 2$ .

MR Zbl

@article{JTNB_2001__13_2_421_0,
     author = {Alex Heinis},
     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},
     zbl = {1013.68155},
     mrnumber = {1879667},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/item/JTNB_2001__13_2_421_0/}
}

TY  - JOUR
AU  - Alex Heinis
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  - https://jtnb.centre-mersenne.org/item/JTNB_2001__13_2_421_0/
LA  - en
ID  - JTNB_2001__13_2_421_0
ER  -

%0 Journal Article
%A Alex Heinis
%T On low-complexity bi-infinite words and their factors
%J Journal de théorie des nombres de Bordeaux
%D 2001
%P 421-442
%V 13
%N 2
%I Université Bordeaux I
%U https://jtnb.centre-mersenne.org/item/JTNB_2001__13_2_421_0/
%G en
%F JTNB_2001__13_2_421_0

Alex Heinis. On low-complexity bi-infinite words and their factors. Journal de théorie des nombres de Bordeaux, Tome 13 (2001) no. 2, pp. 421-442. https://jtnb.centre-mersenne.org/item/JTNB_2001__13_2_421_0/

Bibliographie
Cité par

[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 | Zbl

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

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

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

[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 | Zbl

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

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

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

[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 | Zbl

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

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

[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 | Zbl

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

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

(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 | Zbl

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

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

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