No CrossRef data available.
Article contents
A note on constructing infinite binary words with polynomial subword complexity∗
Published online by Cambridge University Press: 25 April 2013
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 β > 1.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences 2013
References
Allouche, J.-P., Sur la complexité des suites infinies. Bull. Belgian Math. Soc. 1 (1994) 133–143. Google Scholar
J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003).
Arnoux, P., Mauduit, C., Shiokawa, I. and Tamura, J., Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France 122 (1994) 1–12. Google Scholar
Arnoux, P., Mauduit, C., Shiokawa, I. and Tamura, J., Rauzy’s conjecture on billiards in the cube. Tokyo J. Math. 17 (1994) 211–218. Google Scholar
Arnoux, P. and Rauzy, G., Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991) 199–215. Google Scholar
Baryshnikov, Y., Complexity of trajectories in rectangular billiards. Communicat. Math. Phys. 174 (1995) 43–56. Google Scholar
Bedaride, N., Directional billiard complexity in rational polyhedra. Regular Chaotic Dyn. 3 (2003) 97–106. Google Scholar
Blanchet-Sadri, F., Chakarov, A., Manuelli, L., Schwartz, J. and Stich, S., Constructing partial words with subword complexities not achievable by full words. Theoret. Comput. Sci. 432 (2012) 21–27. Google Scholar
Cassaigne, J., Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 4 (1997) 67–88. Google Scholar
Cassaigne, J., 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. Google Scholar
Cassaigne, J. and Karhumäki, J., Toeplitz words, generalized periodicity and periodically iterated morphisms. European J. Combin. 18 (1997) 497–510. Google Scholar
Ferenczi, S., Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145–154. Google Scholar
Gheorghiciuc, I., The subword complexity of a class of infinite binary words. Adv. Appl. Math. 39 (2007) 237–259. Google Scholar
M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002).
Morse, M. and Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. Google Scholar