Standard factors of sturmian words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 1, pp. 159-174.

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.

DOI : 10.1051/ita/2010011
Classification : 68R15
Mots-clés : sturmian words, standard factors, morphisms, palindromes 
@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},
     pages = {159--174},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {1},
     year = {2010},
     doi = {10.1051/ita/2010011},
     mrnumber = {2604941},
     zbl = {1184.68378},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2010011/}
}
TY  - JOUR
AU  - Richomme, Gwénaël
AU  - Saari, Kalle
AU  - Zamboni, Luca Q.
TI  - Standard factors of sturmian words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 159
EP  - 174
VL  - 44
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2010011/
DO  - 10.1051/ita/2010011
LA  - en
ID  - ITA_2010__44_1_159_0
ER  - 
%0 Journal Article
%A Richomme, Gwénaël
%A Saari, Kalle
%A Zamboni, Luca Q.
%T Standard factors of sturmian words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 159-174
%V 44
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2010011/
%R 10.1051/ita/2010011
%G en
%F 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) no. 1, pp. 159-174. doi : 10.1051/ita/2010011. http://www.numdam.org/articles/10.1051/ita/2010011/

[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

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

[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

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

[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

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

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

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

[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

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

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

[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

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

[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

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

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

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

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

[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

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

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

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

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

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

Cité par Sources :