# On low-complexity bi-infinite words and their factors

Journal de théorie des nombres de Bordeaux (2001)

- Volume: 13, Issue: 2, page 421-442
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

topHeinis, Alex. "On low-complexity bi-infinite words and their factors." Journal de théorie des nombres de Bordeaux 13.2 (2001): 421-442. <http://eudml.org/doc/248689>.

@article{Heinis2001,

abstract = {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 $\ge 2^\{n/2\}$ when $k \ge 2$.},

author = {Heinis, Alex},

journal = {Journal de théorie des nombres de Bordeaux},

keywords = {bi-infinite words},

language = {eng},

number = {2},

pages = {421-442},

publisher = {Université Bordeaux I},

title = {On low-complexity bi-infinite words and their factors},

url = {http://eudml.org/doc/248689},

volume = {13},

year = {2001},

}

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

PB - Université Bordeaux I

VL - 13

IS - 2

SP - 421

EP - 442

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

LA - eng

KW - bi-infinite words

UR - http://eudml.org/doc/248689

ER -

## References

top- [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. France119 (1991), 199-215. Zbl0789.28011MR1116845
- [B/dL] J. Berstel, A. De Luca, Sturmian words, Lyndon words and trees. Theoret. Comput. Sc.178 (1993), 171-203. Zbl0901.68155MR1453849
- [B/P] J. Berstel, D. Perrin, Theory of Codes. Academic Press, 1985. Zbl0587.68066MR797069
- [B/Po] J. Berstel, M. Pocchiola, A geometric proof of the enumeration formula for Sturmian words. J. Algebra Comput.3 (1993), 349-355. Zbl0802.68099MR1240390
- [Bo/L] J.-P. Borel, F. Laubie, Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux5 (1993), 23-51. Zbl0839.11008MR1251226
- [Br] T.C. Brown, Descriptions of the characteristic sequence of an arrational. Canad. Math. Bull.36 (1993), 15-21. Zbl0804.11021MR1205889
- [C] E.M. Coven, Sequences with minimal block growth II. Math. Systems Th.8 (1975), 376-382. Zbl0299.54032MR391053
- [C/H] E.M. Coven, G.A. Hedlund, Sequences with minimal block growth. Math. Systems Th.7 (1971), 138-153. Zbl0256.54028MR322838
- [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. Zbl0913.68163MR1678793
- [D/GB] S. Dulucq, D. Gouyou-Beauchamps, Sur les facteurs des suites de Sturm. Theoret. Comput. Sc.71 (1990), 381-400. Zbl0694.68048MR1057771
- [H/W] G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers. Oxford Univ. Press, Third Edition, 1954. Zbl0058.03301MR67125
- [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. Zbl0874.68245MR1311214
- [H/H] M. Morse, G.A. Hedlund, Symbolic dynamics II - Sturmian trajectories. Amer. J. Math.62 (1940), 1-42. Zbl0022.34003MR745JFM66.0188.03
- [Mi] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sc.82 (1991), 71-84. Zbl0728.68093MR1112109
- (Mi/S] F. Mignosi, P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux5 (1993), 211-233. Zbl0797.11029MR1265903
- [P] M.E. Paul, Minimal symbolic flows having minimal block growth. Math. Systems Th.8 (1975), 309-315. Zbl0306.54056MR380760
- [S] K.B. Stolarsky, Beatty sequences, continued fractions and certain shift operators. Canad. Math. Bull.19 (1976), 473-482. Zbl0359.10028MR444558
- [T] R. Tijdeman, Intertwinings of periodic sequences. Indag. Math.9 (1998), 113-122. Zbl0918.11012MR1618219

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.