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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2014019/
[1] On the number of factors in codings of three interval exchange, Discr. Math. Theoret. Comput. Sci. 13 (2011) 51-66. | MR | Zbl
, , and ,[2] A geometric approach to subpixel registration accuracy. Comput. Vision Graph. 40 (1987) 334-360.
, , and ,[3] A geometric proof of the enumeration formula for Sturmian words. Int. J. Algebra Comput. 3 (1993) 349-355. | MR | Zbl
and ,[4] Random generation of finite Sturmian words. Discr. Math. 153 (1996) 29-39. | MR | Zbl
and ,[5] Coding rotations on intervals. Theoret. Comput. Sci. 281 (2002) 99-107. | MR | Zbl
and ,[6] On the arithmetical complexity of Sturmian words. Theoret. Comput. Sci. 380 (2007) 304-316. | MR | Zbl
and ,[7] 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] A classification of binary collections and properties of homogeneity classes. Problemy Kibernet. 39 (1982) 67-84 (in Russian). | MR | Zbl
,[9] Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). | MR | Zbl
,[10] On the number of factors of Sturmian words. Theoret. Comput. Sci. 82 (1991) 71-84. | MR | Zbl
,[11] Sequences with subword complexity 2n, J. Number Theory 46 (1994) 196-213. | MR | Zbl
,Cité par Sources :