No CrossRef data available.
Article contents
Standard factors of Sturmian words
Published online by Cambridge University Press: 11 February 2010
Abstract
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.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 1: Special issue dedicated to the 12th "Journées Montoises d'Informatique Théorique" , January 2010 , pp. 159 - 174
- Copyright
- © EDP Sciences, 2010
References
J.-P. Allouche and V. Berthé, Words in number theory, edited by M. Lothaire. Applied Combinatorics on Words, Cambridge University Press (2005) 520–574.
J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press (2003).
Altman, E., Gaujal, B. and Hordijk, A., Balanced sequences and optimal routing.
J. ACM
47 (2000) 752–775.
CrossRef
P. Arnoux, Sturmian sequences, edited by P. Fogg. Substitutions in dynamics, arithmetics and combinatorics, Lect. Notes Math. 1794 (2002) 143–198.
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.
Berstel, J. and de Luca, A., Sturmian words. Lyndon words and trees.
Theoret. Comput. Sci.
178 (1997) 171–203.
CrossRef
J. Berstel and P. Séébold, Sturmian words, edited by M. Lothaire. Algebraic combinatorics on words, Cambridge University Press (2002) 45–110.
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).
Berthé, V., Holton, C. and Zamboni, L.Q., Initial powers of Sturmian sequences.
Acta Inform.
122 (2006) 315–347.
Bombieri, E. and Taylor, J.E., Which distributions of matter diffract? An initial investigation.
J. Phys.
47 (1986) 19–28.
Cassaigne, J., On extremal properties of the Fibonacci word.
RAIRO-Theor. Inf. Appl.
42 (2008) 701–715.
CrossRef
C. Choffrut and J. Karhumäki, Combinatorics of words, edited by G. Rozenberg and A. Salomaa. Handbook of Formal Languages
1, Springer (1997).
Chuan, W.-f.,
Unbordered factors of the characteristic sequences of irrational numbers.
Theoret. Comput. Sci.
205 (1998) 337–344.
CrossRef
Currie, J.D. and Saari, K., Least periods of factors of infinite words.
RAIRO-Theor. Inf. Appl.
43 (2009) 165–178.
CrossRef
de Luca, A., Sturmian words: structure, combinatorics, and their arithmetics.
Theoret. Comput. Sci.
183 (1997) 45–82.
CrossRef
Droubay, X., Justin, J. and Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy.
Theoret. Comput. Sci.
255 (2001) 539–553.
CrossRef
Glen, A. and Justin, J., Episturmian words: a survey.
RAIRO-Theor. Inf. Appl.
43 (2009) 403–442.
CrossRef
Glen, A., Levé, F. and Richomme, G., Directive words of episturmian words: equivalence and normalization.
RAIRO-Theor. Inf. Appl.
43 (2009) 299–319.
CrossRef
Harju, T. and Nowotka, D., Minimal Duval Extensions.
Int. J. Found. Comput. Sci.
15 (2004) 349–354.
CrossRef
Klette, R. and Rosenfeld, A., Digital straightness – a review.
Discrete Appl. Math.
139 (2004) 197–230.
CrossRef
M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002).
Mignosi, F. and Zamboni, L.Q., A note on a conjecture of Duval and Sturmian words.
RAIRO-Theor. Inf. Appl.
36 (2002) 1–3.
CrossRef
Morse, M. and Hedlund, G.A., Symbolic dynamics II: Sturmian trajectories.
Amer. J. Math.
62 (1940) 1–42.
CrossRef
Richomme, G., Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words.
Theoret. Comput. Sci.
380 (2007) 393–400.
CrossRef
K. Saari, Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes Comput. Sci.
4649 (2007) 363–372.
K. Saari, On the frequency and periodicity of infinite words. Ph.D. Thesis, University of Turku, TUCS Dissertations 97 (2008).