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

Abstract

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

How to cite

top

Richomme, 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
  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.  
  2. J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press (2003).  
  3. E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing. J. ACM47 (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.  
  6. J. Berstel and A. de Luca, Sturmian words. Lyndon words and trees. Theoret. Comput. Sci.178 (1997) 171–203.  
  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).  
  9. V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Inform.122 (2006) 315–347.  
  10. E. Bombieri and J.E. Taylor, Which distributions of matter diffract? An initial investigation. J. Phys.47 (1986) 19–28.  
  11. J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl.42 (2008) 701–715.  
  12. C. Choffrut and J. Karhumäki, Combinatorics of words, edited by G. Rozenberg and A. Salomaa. Handbook of Formal Languages1, Springer (1997).  
  13. W.-f. Chuan, Unbordered factors of the characteristic sequences of irrational numbers. Theoret. Comput. Sci.205 (1998) 337–344.  
  14. J.D. Currie and K. Saari, Least periods of factors of infinite words. RAIRO-Theor. Inf. Appl.43 (2009) 165–178.  
  15. A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci.183 (1997) 45–82.  
  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.  
  17. A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl.43 (2009) 403–442.  
  18. A. Glen, F. Levé and G. Richomme, Directive words of episturmian words: equivalence and normalization. RAIRO-Theor. Inf. Appl.43 (2009) 299–319.  
  19. T. Harju and D. Nowotka, Minimal Duval Extensions. Int. J. Found. Comput. Sci.15 (2004) 349–354.  
  20. R. Klette and A. Rosenfeld, Digital straightness – a review. Discrete Appl. Math.139 (2004) 197–230.  
  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.  
  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.  
  24. M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866.  
  25. M. Morse and G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math.62 (1940) 1–42.  
  26. G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci.380 (2007) 393–400.  
  27. K. Saari, Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes Comput. Sci.4649 (2007) 363–372.  
  28. K. Saari, On the frequency and periodicity of infinite words. Ph.D. Thesis, University of Turku, TUCS Dissertations 97 (2008).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.