A note on constructing infinite binary words with polynomial subword complexity

Francine Blanchet-Sadri; Bob Chen; Sinziana Munteanu

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 2, page 195-199
  • ISSN: 0988-3754

Abstract

top
Most of the constructions of infinite words having polynomial subword complexity are quite complicated, e.g., sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words w over a binary alphabet  { a,b }  with polynomial subword complexity pw. Assuming w contains an infinite number of a’s, our method is based on the gap function which gives the distances between consecutive b’s. It is known that if the gap function is injective, we can obtain at most quadratic subword complexity, and if the gap function is blockwise injective, we can obtain at most cubic subword complexity. Here, we construct infinite binary words w such that pw(n) = Θ(nβ) for any real number β > 1.

How to cite

top

Blanchet-Sadri, Francine, Chen, Bob, and Munteanu, Sinziana. "A note on constructing infinite binary words with polynomial subword complexity." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.2 (2013): 195-199. <http://eudml.org/doc/273080>.

@article{Blanchet2013,
abstract = {Most of the constructions of infinite words having polynomial subword complexity are quite complicated, e.g., sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words w over a binary alphabet  \{ a,b \}  with polynomial subword complexity pw. Assuming w contains an infinite number of a’s, our method is based on the gap function which gives the distances between consecutive b’s. It is known that if the gap function is injective, we can obtain at most quadratic subword complexity, and if the gap function is blockwise injective, we can obtain at most cubic subword complexity. Here, we construct infinite binary words w such that pw(n) = Θ(nβ) for any real number β &gt; 1.},
author = {Blanchet-Sadri, Francine, Chen, Bob, Munteanu, Sinziana},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {binary words; subword complexity; gap function},
language = {eng},
number = {2},
pages = {195-199},
publisher = {EDP-Sciences},
title = {A note on constructing infinite binary words with polynomial subword complexity},
url = {http://eudml.org/doc/273080},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Blanchet-Sadri, Francine
AU - Chen, Bob
AU - Munteanu, Sinziana
TI - A note on constructing infinite binary words with polynomial subword complexity
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 2
SP - 195
EP - 199
AB - Most of the constructions of infinite words having polynomial subword complexity are quite complicated, e.g., sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words w over a binary alphabet  { a,b }  with polynomial subword complexity pw. Assuming w contains an infinite number of a’s, our method is based on the gap function which gives the distances between consecutive b’s. It is known that if the gap function is injective, we can obtain at most quadratic subword complexity, and if the gap function is blockwise injective, we can obtain at most cubic subword complexity. Here, we construct infinite binary words w such that pw(n) = Θ(nβ) for any real number β &gt; 1.
LA - eng
KW - binary words; subword complexity; gap function
UR - http://eudml.org/doc/273080
ER -

References

top
  1. [1] J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belgian Math. Soc.1 (1994) 133–143. Zbl0803.68094MR1318964
  2. [2] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). Zbl1086.11015MR1997038
  3. [3] P. Arnoux, C. Mauduit, I. Shiokawa and J. Tamura, Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France122 (1994) 1–12. Zbl0791.58034MR1259106
  4. [4] P. Arnoux, C. Mauduit, I. Shiokawa and J. Tamura, Rauzy’s conjecture on billiards in the cube. Tokyo J. Math.17 (1994) 211–218. Zbl0814.11014MR1279582
  5. [5] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199–215. Zbl0789.28011MR1116845
  6. [6] Y. Baryshnikov, Complexity of trajectories in rectangular billiards. Communicat. Math. Phys.174 (1995) 43–56. Zbl0839.11006MR1372799
  7. [7] N. Bedaride, Directional billiard complexity in rational polyhedra. Regular Chaotic Dyn.3 (2003) 97–106. Zbl1023.37024MR1963971
  8. [8] F. Blanchet-Sadri, A. Chakarov, L. Manuelli, J. Schwartz and S. Stich, Constructing partial words with subword complexities not achievable by full words. Theoret. Comput. Sci.432 (2012) 21–27. Zbl1244.68063MR2914176
  9. [9] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc.4 (1997) 67–88. Zbl0921.68065MR1440670
  10. [10] J. Cassaigne, Constructing infinite words of intermediate complexity. In DLT 2002, 6th International Conference on Developments in Language Theory, Kyoto, Japan. Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 2450 (2003) 173–184. Zbl1015.68138MR2177342
  11. [11] J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. European J. Combin.18 (1997) 497–510. Zbl0881.68065MR1455183
  12. [12] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154. Zbl0936.37008MR1665394
  13. [13] I. Gheorghiciuc, The subword complexity of a class of infinite binary words. Adv. Appl. Math.39 (2007) 237–259. Zbl1117.68059MR2333650
  14. [14] M. Koskas, Complexité des suites de Toeplitz. Discrete Math.183 (1998) 161–183. Zbl0895.11011
  15. [15] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). Zbl1221.68183MR1905123
  16. [16] M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866. Zbl0019.33502MR1507944JFM64.0798.04
  17. [17] M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. Zbl0022.34003MR745JFM66.0188.03
  18. [18] G. Rote, Sequences with subword complexity 2n. J. Number Theory46 (1993) 196–213. Zbl0804.11023MR1269252

NotesEmbed ?

top

You must be logged in to post comments.