On low-complexity bi-infinite words and their factors

Alex Heinis

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

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

Abstract

top
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 k ≥ 2 .

How to cite

top

Heinis, 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
  1. [A] P. Alessandri, Codages de rotations et de basses complexités. Thèse de Doctorat, Université d'Aix-Marseille II, 1996. 
  2. [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
  3. [B/dL] J. Berstel, A. De Luca, Sturmian words, Lyndon words and trees. Theoret. Comput. Sc.178 (1993), 171-203. Zbl0901.68155MR1453849
  4. [B/P] J. Berstel, D. Perrin, Theory of Codes. Academic Press, 1985. Zbl0587.68066MR797069
  5. [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
  6. [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
  7. [Br] T.C. Brown, Descriptions of the characteristic sequence of an arrational. Canad. Math. Bull.36 (1993), 15-21. Zbl0804.11021MR1205889
  8. [C] E.M. Coven, Sequences with minimal block growth II. Math. Systems Th.8 (1975), 376-382. Zbl0299.54032MR391053
  9. [C/H] E.M. Coven, G.A. Hedlund, Sequences with minimal block growth. Math. Systems Th.7 (1971), 138-153. Zbl0256.54028MR322838
  10. [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
  11. [D/GB] S. Dulucq, D. Gouyou-Beauchamps, Sur les facteurs des suites de Sturm. Theoret. Comput. Sc.71 (1990), 381-400. Zbl0694.68048MR1057771
  12. [H/W] G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers. Oxford Univ. Press, Third Edition, 1954. Zbl0058.03301MR67125
  13. [H/T] A. Heinis, R. Tijdeman, Extending balanced and stiff words. Report no. W97-15, University of Leiden, 1997. 
  14. [dL/Mi] A. De Luca, F. Mignosi, Some combinatorial properties of Sturmian words. Theoret. Comput. Sc.136 (1994), 361-385. Zbl0874.68245MR1311214
  15. [H/H] M. Morse, G.A. Hedlund, Symbolic dynamics II - Sturmian trajectories. Amer. J. Math.62 (1940), 1-42. Zbl0022.34003MR745JFM66.0188.03
  16. [Mi] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sc.82 (1991), 71-84. Zbl0728.68093MR1112109
  17. (Mi/S] F. Mignosi, P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux5 (1993), 211-233. Zbl0797.11029MR1265903
  18. [P] M.E. Paul, Minimal symbolic flows having minimal block growth. Math. Systems Th.8 (1975), 309-315. Zbl0306.54056MR380760
  19. [S] K.B. Stolarsky, Beatty sequences, continued fractions and certain shift operators. Canad. Math. Bull.19 (1976), 473-482. Zbl0359.10028MR444558
  20. [T] R. Tijdeman, Intertwinings of periodic sequences. Indag. Math.9 (1998), 113-122. Zbl0918.11012MR1618219

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.