# Standard factors of Sturmian words

Gwénaël Richomme; Kalle Saari; Luca Q. Zamboni

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 44, Issue: 1, page 159-174
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topRichomme, Gwénaël, Saari, Kalle, and Zamboni, Luca Q.. "Standard factors of Sturmian words." RAIRO - Theoretical Informatics and Applications 44.1 (2010): 159-174. <http://eudml.org/doc/250802>.

@article{Richomme2010,

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.
},

author = {Richomme, Gwénaël, Saari, Kalle, Zamboni, Luca Q.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Sturmian words; standard factors; morphisms; palindromes},

language = {eng},

month = {2},

number = {1},

pages = {159-174},

publisher = {EDP Sciences},

title = {Standard factors of Sturmian words},

url = {http://eudml.org/doc/250802},

volume = {44},

year = {2010},

}

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

DA - 2010/2//

PB - EDP Sciences

VL - 44

IS - 1

SP - 159

EP - 174

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

LA - eng

KW - Sturmian words; standard factors; morphisms; palindromes

UR - http://eudml.org/doc/250802

ER -

## References

top- 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). Zbl1086.11015
- E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing. J. ACM47 (2000) 752–775. Zbl1327.68180
- 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.
- J. Berstel and A. de Luca, Sturmian words. Lyndon words and trees. Theoret. Comput. Sci.178 (1997) 171–203. Zbl0901.68155
- 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). Zbl1161.68043
- V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Inform.122 (2006) 315–347. Zbl1117.37005
- E. Bombieri and J.E. Taylor, Which distributions of matter diffract? An initial investigation. J. Phys.47 (1986) 19–28. Zbl0693.52002
- J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl.42 (2008) 701–715. Zbl1155.68062
- C. Choffrut and J. Karhumäki, Combinatorics of words, edited by G. Rozenberg and A. Salomaa. Handbook of Formal Languages1, Springer (1997). Zbl0964.68119
- W.-f. Chuan, Unbordered factors of the characteristic sequences of irrational numbers. Theoret. Comput. Sci.205 (1998) 337–344. Zbl0913.68119
- J.D. Currie and K. Saari, Least periods of factors of infinite words. RAIRO-Theor. Inf. Appl.43 (2009) 165–178. Zbl1162.68510
- A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci.183 (1997) 45–82. Zbl0911.68098
- X. Droubay, J. Justin and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci.255 (2001) 539–553. Zbl0981.68126
- A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl.43 (2009) 403–442. Zbl1182.68155
- A. Glen, F. Levé and G. Richomme, Directive words of episturmian words: equivalence and normalization. RAIRO-Theor. Inf. Appl.43 (2009) 299–319. Zbl1166.68034
- T. Harju and D. Nowotka, Minimal Duval Extensions. Int. J. Found. Comput. Sci.15 (2004) 349–354. Zbl1067.68112
- R. Klette and A. Rosenfeld, Digital straightness – a review. Discrete Appl. Math.139 (2004) 197–230. Zbl1093.68656
- M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). Zbl1001.68093
- G. Melançon, Lyndon factorization of Sturmian words. Discrete Math.210 (2000) 137–149. Zbl0946.68113
- F. Mignosi and L.Q. Zamboni, A note on a conjecture of Duval and Sturmian words. RAIRO-Theor. Inf. Appl.36 (2002) 1–3. Zbl1013.68152
- M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866. Zbl0019.33502
- M. Morse and G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math.62 (1940) 1–42. Zbl0022.34003
- G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci.380 (2007) 393–400. Zbl1118.68111
- K. Saari, Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes Comput. Sci.4649 (2007) 363–372. Zbl1188.68218
- K. Saari, On the frequency and periodicity of infinite words. Ph.D. Thesis, University of Turku, TUCS Dissertations 97 (2008).

## NotesEmbed ?

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