article · Springer Link (Chiba Institute of Technology) · 2013

A note on constructing infinite binary words with polynomial subword complexity

Francine Blanchet-Sadri, Bob Chen, Sinziana Munteanu

Cited by 0Abstract and details only

Abstract

\n 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.\n

Cite this paper

APA 7

Blanchet-Sadri, F., Chen, B., & Munteanu, S. (2013). A note on constructing infinite binary words with polynomial subword complexity. Springer Link (Chiba Institute of Technology). https://doi.org/10.1051/ita/2013033/pdf

MLA 9

Blanchet-Sadri, Francine, et al. “A note on constructing infinite binary words with polynomial subword complexity.” Springer Link (Chiba Institute of Technology), 2013, https://doi.org/10.1051/ita/2013033/pdf.

Chicago

Blanchet-Sadri, Francine, Bob Chen, and Sinziana Munteanu. 2013. “A note on constructing infinite binary words with polynomial subword complexity.” Springer Link (Chiba Institute of Technology). https://doi.org/10.1051/ita/2013033/pdf.

Harvard

Blanchet-Sadri, F., Chen, B. and Munteanu, S. (2013) ‘A note on constructing infinite binary words with polynomial subword complexity’, Springer Link (Chiba Institute of Technology). Available at: https://doi.org/10.1051/ita/2013033/pdf.

BibTeX

@article{blanchetsadri2013note,
  title = {{A note on constructing infinite binary words with polynomial subword complexity}},
  author = {Blanchet-Sadri, Francine and Chen, Bob and Munteanu, Sinziana},
  journal = {Springer Link (Chiba Institute of Technology)},
  year = {2013},
  doi = {10.1051/ita/2013033/pdf}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.