The number of binary rotation words

A. Frid; D. Jamet

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

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

Abstract

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

How to cite

top

Frid, 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. [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. [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. [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. [4] J. Berstel and M. Pocchiola, Random generation of finite Sturmian words. Discr. Math.153 (1996) 29–39. Zbl0848.68078MR1394943
  5. [5] J. Berstel and L. Vuillon, Coding rotations on intervals. Theoret. Comput. Sci.281 (2002) 99–107. Zbl0997.68094MR1909570
  6. [6] J. Cassaigne and A.E. Frid, On the arithmetical complexity of Sturmian words. Theoret. Comput. Sci.380 (2007) 304–316. Zbl1119.68138MR2331000
  7. [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. [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. [9] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). Zbl1221.68183MR1905123
  10. [10] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sci.82 (1991) 71–84. Zbl0728.68093MR1112109
  11. [11] G. Rote, Sequences with subword complexity 2n, J. Number Theory46 (1994) 196–213. Zbl0804.11023MR1269252

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.