The number of binary rotation words
Frid, A. ; Jamet, D.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014), p. 453-465 / Harvested from Numdam
Access to full text

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.

Publié le : 2014-01-01
DOI : https://doi.org/10.1051/ita/2014019
Classification:  68R15,  37B10 
@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},
     volume = {48},
     year = {2014},
     pages = {453-465},
     doi = {10.1051/ita/2014019},
     mrnumber = {3302497},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 453-465. doi : 10.1051/ita/2014019. http://gdmltest.u-ga.fr/item/ITA_2014__48_4_453_0/

[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 2854338 | Zbl 1283.68274

[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 1240390 | Zbl 0802.68099

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

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

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

[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 2131762 | Zbl 1125.68091

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

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

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

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