The number of binary rotation words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 4, pp. 453-465.

We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length n. We also give the precise asymptotics for it, which happens to be Θ(n4). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [Problemy Kibernet. 39 (1982) 67-84], then independently by Mignosi [Theoret. Comput. Sci. 82 (1991) 71-84], and others.

DOI : 10.1051/ita/2014019
Classification : 68R15, 37B10
Mots-clés : rotation, rotation words, Sturmian words, subword complexity, total complexity 
@article{ITA_2014__48_4_453_0,
     author = {Frid, A. and Jamet, D.},
     title = {The number of binary rotation words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {453--465},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {4},
     year = {2014},
     doi = {10.1051/ita/2014019},
     mrnumber = {3302497},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2014019/}
}
TY  - JOUR
AU  - Frid, A.
AU  - Jamet, D.
TI  - The number of binary rotation words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2014
SP  - 453
EP  - 465
VL  - 48
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2014019/
DO  - 10.1051/ita/2014019
LA  - en
ID  - ITA_2014__48_4_453_0
ER  - 
%0 Journal Article
%A Frid, A.
%A Jamet, D.
%T The number of binary rotation words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2014
%P 453-465
%V 48
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2014019/
%R 10.1051/ita/2014019
%G en
%F ITA_2014__48_4_453_0
Frid, A.; Jamet, D. The number of binary rotation words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 4, pp. 453-465. doi : 10.1051/ita/2014019. http://www.numdam.org/articles/10.1051/ita/2014019/

[1] P. Ambrož, A. Frid, Z. Masáková and E. Pelantová, On the number of factors in codings of three interval exchange, Discr. Math. Theoret. Comput. Sci. 13 (2011) 51-66. | MR | Zbl

[2] C.A. Berenstein, L.N. Kanal, D. Lavine and E.C. Olson, A geometric approach to subpixel registration accuracy. Comput. Vision Graph. 40 (1987) 334-360.

[3] J. Berstel and M. Pocchiola, A geometric proof of the enumeration formula for Sturmian words. Int. J. Algebra Comput. 3 (1993) 349-355. | MR | Zbl

[4] J. Berstel and M. Pocchiola, Random generation of finite Sturmian words. Discr. Math. 153 (1996) 29-39. | MR | Zbl

[5] J. Berstel and L. Vuillon, Coding rotations on intervals. Theoret. Comput. Sci. 281 (2002) 99-107. | MR | Zbl

[6] J. Cassaigne and A.E. Frid, On the arithmetical complexity of Sturmian words. Theoret. Comput. Sci. 380 (2007) 304-316. | MR | Zbl

[7] A. Frid, A lower bound for the arithmetical complexity of Sturmian words, Siberian Electron. Math. Rep. 2 (2005) 14-22 (in Russian, English abstract). | MR | Zbl

[8] E.P. Lipatov, A classification of binary collections and properties of homogeneity classes. Problemy Kibernet. 39 (1982) 67-84 (in Russian). | MR | Zbl

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

[10] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sci. 82 (1991) 71-84. | MR | Zbl

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

Cité par Sources :