Standard factors of sturmian words
Richomme, Gwénaël ; Saari, Kalle ; Zamboni, Luca Q.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010), p. 159-174 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Among the various ways to construct a characteristic sturmian word, one of the most used consists in defining an infinite sequence of prefixes that are standard. Nevertheless in any characteristic word c, some standard words occur that are not prefixes of c. We characterize all standard words occurring in any characteristic word (and so in any sturmian word) using firstly morphisms, then standard prefixes and finally palindromes.

Publié le : 2010-01-01
DOI : https://doi.org/10.1051/ita/2010011
Classification:  68R15 
@article{ITA_2010__44_1_159_0,
     author = {Richomme, Gw\'ena\"el and Saari, Kalle and Zamboni, Luca Q.},
     title = {Standard factors of sturmian words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {44},
     year = {2010},
     pages = {159-174},
     doi = {10.1051/ita/2010011},
     mrnumber = {2604941},
     zbl = {1184.68378},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2010__44_1_159_0}
}

Richomme, Gwénaël; Saari, Kalle; Zamboni, Luca Q. Standard factors of sturmian words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 159-174. doi : 10.1051/ita/2010011. http://gdmltest.u-ga.fr/item/ITA_2010__44_1_159_0/

[1] J.-P. Allouche and V. Berthé, Words in number theory, edited by M. Lothaire. Applied Combinatorics on Words, Cambridge University Press (2005) 520-574. | Zbl 1133.68067

[2] J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press (2003). | Zbl 1086.11015

[3] E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing. J. ACM 47 (2000) 752-775.

[4] P. Arnoux, Sturmian sequences, edited by P. Fogg. Substitutions in dynamics, arithmetics and combinatorics, Lect. Notes Math. 1794 (2002) 143-198.

[5] J. Berstel, Sturmian and episturmian Words (a survey of some recent results), edited by S. Bozapalidis and G. Rahonis. Conference on algebraic informatics (CAI'07), Lect. Notes Comput. Sci. 4728 (2007) 23-47. | Zbl 1149.68065

[6] J. Berstel and A. De Luca, Sturmian words. Lyndon words and trees. Theoret. Comput. Sci. 178 (1997) 171-203. | Zbl 0901.68155

[7] J. Berstel and P. Séébold, Sturmian words, edited by M. Lothaire. Algebraic combinatorics on words, Cambridge University Press (2002) 45-110.

[8] J. Berstel, A. Lauve, C. Reutenauer and F. Saliola, Combinatorics on words: Christoffel words and repetition in words. CRM Monograph Series, Vol. 27, CRM-AMS Montréal (2008). | Zbl 1161.68043

[9] V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Inform. 122 (2006) 315-347. | Zbl 1117.37005

[10] E. Bombieri and J.E. Taylor, Which distributions of matter diffract? An initial investigation. J. Phys. 47 (1986) 19-28. | Zbl 0693.52002

[11] J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701-715. | Numdam | Zbl 1155.68062

[12] C. Choffrut and J. Karhumäki, Combinatorics of words, edited by G. Rozenberg and A. Salomaa. Handbook of Formal Languages 1, Springer (1997).

[13] W.-f. Chuan, Unbordered factors of the characteristic sequences of irrational numbers. Theoret. Comput. Sci. 205 (1998) 337-344. | Zbl 0913.68119

[14] J.D. Currie and K. Saari, Least periods of factors of infinite words. RAIRO-Theor. Inf. Appl. 43 (2009) 165-178. | Numdam | Zbl 1162.68510

[15] A. De Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45-82. | Zbl 0911.68098

[16] X. Droubay, J. Justin and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | Zbl 0981.68126

[17] A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl. 43 (2009) 403-442. | Zbl 1182.68155

[18] A. Glen, F. Levé and G. Richomme, Directive words of episturmian words: equivalence and normalization. RAIRO-Theor. Inf. Appl. 43 (2009) 299-319. | Numdam | Zbl 1166.68034

[19] T. Harju and D. Nowotka, Minimal Duval Extensions. Int. J. Found. Comput. Sci. 15 (2004) 349-354. | Zbl 1067.68112

[20] R. Klette and A. Rosenfeld, Digital straightness - a review. Discrete Appl. Math. 139 (2004) 197-230. | Zbl 1093.68656

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

[22] G. Melançon, Lyndon factorization of Sturmian words. Discrete Math. 210 (2000) 137-149. | Zbl 0946.68113

[23] F. Mignosi and L.Q. Zamboni, A note on a conjecture of Duval and Sturmian words. RAIRO-Theor. Inf. Appl. 36 (2002) 1-3. | Numdam | Zbl 1013.68152

[24] M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM 64.0798.04

[25] M. Morse and G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03

[26] G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393-400. | Zbl 1118.68111

[27] K. Saari, Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes Comput. Sci. 4649 (2007) 363-372. | Zbl 1188.68218

[28] K. Saari, On the frequency and periodicity of infinite words. Ph.D. Thesis, University of Turku, TUCS Dissertations 97 (2008).