Voir la notice de l'article provenant de la source Numdam
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.
@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},
mrnumber = {3072318},
zbl = {1266.68146},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2013033/}
}
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 SP - 195 EP - 199 VL - 47 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2013033/ DO - 10.1051/ita/2013033 LA - en ID - ITA_2013__47_2_195_0 ER -
%0 Journal Article %A Blanchet-Sadri, Francine %A Chen, Bob %A Munteanu, Sinziana %T A note on constructing infinite binary words with polynomial subword complexity %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2013 %P 195-199 %V 47 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2013033/ %R 10.1051/ita/2013033 %G en %F ITA_2013__47_2_195_0
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
Cité par Sources :