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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2010011/
[1] Words in number theory, edited by M. Lothaire. Applied Combinatorics on Words, Cambridge University Press (2005) 520-574. | Zbl
and ,[2] Automatic sequences. Cambridge University Press (2003). | Zbl
and ,[3] Balanced sequences and optimal routing. J. ACM 47 (2000) 752-775.
, and ,[4] Sturmian sequences, edited by P. Fogg. Substitutions in dynamics, arithmetics and combinatorics, Lect. Notes Math. 1794 (2002) 143-198.
,[5] 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] Sturmian words. Lyndon words and trees. Theoret. Comput. Sci. 178 (1997) 171-203. | Zbl
and ,[7] Sturmian words, edited by M. Lothaire. Algebraic combinatorics on words, Cambridge University Press (2002) 45-110.
and ,[8] Combinatorics on words: Christoffel words and repetition in words. CRM Monograph Series, Vol. 27, CRM-AMS Montréal (2008). | Zbl
, , and ,[9] Initial powers of Sturmian sequences. Acta Inform. 122 (2006) 315-347. | Zbl
, and ,[10] Which distributions of matter diffract? An initial investigation. J. Phys. 47 (1986) 19-28. | Zbl
and ,[11] On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701-715. | Numdam | Zbl
,[12] Combinatorics of words, edited by G. Rozenberg and A. Salomaa. Handbook of Formal Languages 1, Springer (1997).
and ,[13] W.-f. Chuan, Unbordered factors of the characteristic sequences of irrational numbers. Theoret. Comput. Sci. 205 (1998) 337-344. | Zbl
[14] Least periods of factors of infinite words. RAIRO-Theor. Inf. Appl. 43 (2009) 165-178. | Numdam | Zbl
and ,[15] Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45-82. | Zbl
,[16] Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | Zbl
, and ,[17] Episturmian words: a survey. RAIRO-Theor. Inf. Appl. 43 (2009) 403-442. | Zbl
and ,[18] Directive words of episturmian words: equivalence and normalization. RAIRO-Theor. Inf. Appl. 43 (2009) 299-319. | Numdam | Zbl
, and ,[19] Minimal Duval Extensions. Int. J. Found. Comput. Sci. 15 (2004) 349-354. | Zbl
and ,[20] Digital straightness - a review. Discrete Appl. Math. 139 (2004) 197-230. | Zbl
and ,[21] Algebraic Combinatorics on Words. Cambridge University Press (2002).
,[22] Lyndon factorization of Sturmian words. Discrete Math. 210 (2000) 137-149. | Zbl
,[23] A note on a conjecture of Duval and Sturmian words. RAIRO-Theor. Inf. Appl. 36 (2002) 1-3. | Numdam | Zbl
and ,[24] Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM
and ,[25] Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM
and ,[26] Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393-400. | Zbl
,[27] Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes Comput. Sci. 4649 (2007) 363-372. | Zbl
,[28] On the frequency and periodicity of infinite words. Ph.D. Thesis, University of Turku, TUCS Dissertations 97 (2008).
,Cité par Sources :