# The number of binary rotation words

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

- Volume: 48, Issue: 4, page 453-465
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topFrid, A., and Jamet, D.. "The number of binary rotation words." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.4 (2014): 453-465. <http://eudml.org/doc/273023>.

@article{Frid2014,

abstract = {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.},

author = {Frid, A., Jamet, D.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {rotation; rotation words; Sturmian words; subword complexity; total complexity},

language = {eng},

number = {4},

pages = {453-465},

publisher = {EDP-Sciences},

title = {The number of binary rotation words},

url = {http://eudml.org/doc/273023},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 4

SP - 453

EP - 465

AB - 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.

LA - eng

KW - rotation; rotation words; Sturmian words; subword complexity; total complexity

UR - http://eudml.org/doc/273023

ER -

## References

top- [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. Zbl1283.68274MR2854338
- [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. Zbl0802.68099MR1240390
- [4] J. Berstel and M. Pocchiola, Random generation of finite Sturmian words. Discr. Math.153 (1996) 29–39. Zbl0848.68078MR1394943
- [5] J. Berstel and L. Vuillon, Coding rotations on intervals. Theoret. Comput. Sci.281 (2002) 99–107. Zbl0997.68094MR1909570
- [6] J. Cassaigne and A.E. Frid, On the arithmetical complexity of Sturmian words. Theoret. Comput. Sci.380 (2007) 304–316. Zbl1119.68138MR2331000
- [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). Zbl1125.68091MR2131762
- [8] E.P. Lipatov, A classification of binary collections and properties of homogeneity classes. Problemy Kibernet. 39 (1982) 67–84 (in Russian). Zbl0555.94007MR694826
- [9] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). Zbl1221.68183MR1905123
- [10] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sci.82 (1991) 71–84. Zbl0728.68093MR1112109
- [11] G. Rote, Sequences with subword complexity 2n, J. Number Theory46 (1994) 196–213. Zbl0804.11023MR1269252

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.