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