A note on constructing infinite binary words with polynomial subword complexity
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 2, pp. 195-199.

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.

DOI : https://doi.org/10.1051/ita/2013033
Classification : 68R15
Mots clés : binary words, subword complexity, gap function
@article{ITA_2013__47_2_195_0,
author = {Blanchet-Sadri, Francine and Chen, Bob and Munteanu, Sinziana},
title = {A note on constructing infinite binary words with polynomial subword complexity},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {195--199},
publisher = {EDP-Sciences},
volume = {47},
number = {2},
year = {2013},
doi = {10.1051/ita/2013033},
zbl = {1266.68146},
mrnumber = {3072318},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2013033/}
}
TY  - JOUR
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
DA  - 2013///
SP  - 195
EP  - 199
VL  - 47
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2013033/
UR  - https://zbmath.org/?q=an%3A1266.68146
UR  - https://www.ams.org/mathscinet-getitem?mr=3072318
UR  - https://doi.org/10.1051/ita/2013033
DO  - 10.1051/ita/2013033
LA  - en
ID  - ITA_2013__47_2_195_0
ER  - 
Blanchet-Sadri, Francine; Chen, Bob; Munteanu, Sinziana. A note on constructing infinite binary words with polynomial subword complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 2, pp. 195-199. doi : 10.1051/ita/2013033. http://www.numdam.org/articles/10.1051/ita/2013033/

[1] J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belgian Math. Soc. 1 (1994) 133-143. | MR 1318964 | Zbl 0803.68094

[2] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). | MR 1997038 | Zbl 1086.11015

[3] P. Arnoux, C. Mauduit, I. Shiokawa and J. Tamura, Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France 122 (1994) 1-12. | Numdam | MR 1259106 | Zbl 0791.58034

[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. | MR 1279582 | Zbl 0814.11014

[5] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR 1116845 | Zbl 0789.28011

[6] Y. Baryshnikov, Complexity of trajectories in rectangular billiards. Communicat. Math. Phys. 174 (1995) 43-56. | MR 1372799 | Zbl 0839.11006

[7] N. Bedaride, Directional billiard complexity in rational polyhedra. Regular Chaotic Dyn. 3 (2003) 97-106. | MR 1963971 | Zbl 1023.37024

[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. | MR 2914176 | Zbl 1244.68063

[9] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 4 (1997) 67-88. | MR 1440670 | Zbl 0921.68065

[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. | MR 2177342 | Zbl 1015.68138

[11] J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. European J. Combin. 18 (1997) 497-510. | MR 1455183 | Zbl 0881.68065

[12] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR 1665394 | Zbl 0936.37008

[13] I. Gheorghiciuc, The subword complexity of a class of infinite binary words. Adv. Appl. Math. 39 (2007) 237-259. | MR 2333650 | Zbl 1117.68059

[14] M. Koskas, Complexité des suites de Toeplitz. Discrete Math. 183 (1998) 161-183. | Zbl 0895.11011

[15] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). | MR 1905123 | Zbl 1221.68183

[16] M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM 64.0798.04 | MR 1507944

[17] M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03 | MR 745

[18] G. Rote, Sequences with subword complexity 2n. J. Number Theory 46 (1993) 196-213. | MR 1269252 | Zbl 0804.11023

Cité par Sources :