Directive words of episturmian words : equivalences and normalization

Amy Glen; Florence Levé; Gwénaël Richomme

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2009)

  • Volume: 43, Issue: 2, page 299-319
  • ISSN: 0988-3754

Abstract

top
Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.

How to cite

top

Glen, Amy, Levé, Florence, and Richomme, Gwénaël. "Directive words of episturmian words : equivalences and normalization." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 43.2 (2009): 299-319. <http://eudml.org/doc/244663>.

@article{Glen2009,
abstract = {Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.},
author = {Glen, Amy, Levé, Florence, Richomme, Gwénaël},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {episturmian word; sturmian word; Arnoux-Rauzy sequence; episturmian morphism; directive word},
language = {eng},
number = {2},
pages = {299-319},
publisher = {EDP-Sciences},
title = {Directive words of episturmian words : equivalences and normalization},
url = {http://eudml.org/doc/244663},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Glen, Amy
AU - Levé, Florence
AU - Richomme, Gwénaël
TI - Directive words of episturmian words : equivalences and normalization
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2009
PB - EDP-Sciences
VL - 43
IS - 2
SP - 299
EP - 319
AB - Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.
LA - eng
KW - episturmian word; sturmian word; Arnoux-Rauzy sequence; episturmian morphism; directive word
UR - http://eudml.org/doc/244663
ER -

References

top
  1. [1] J.-P. Allouche and J. Shallit, Automatic sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). Zbl1086.11015MR1997038
  2. [2] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexités 2 n + 1 . Bull. Soc. Math. France 119 (1991) 199–215. Zbl0789.28011MR1116845
  3. [3] J. Berstel, Sturmian and episturmian words (a survey of some recent results), in Proceedings of CAI 2007. Lect. Notes Comput. Sci., Vol. 4728. Springer-Verlag (2007). Zbl1149.68065
  4. [4] V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315–347. Zbl1117.37005MR2234421
  5. [5] 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.68126MR1819089
  6. [6] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145–154. Zbl0936.37008MR1665394
  7. [7] A. Glen, On Sturmian and episturmian words, and related topics. Ph.D. thesis, The University of Adelaide, Australia (2006). Zbl1102.68516
  8. [8] A. Glen, A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. 391 (2008) 51–60. Zbl1133.68065MR2381351
  9. [9] A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl. (submitted). e-print arxiv:0801.1655 (2007). Zbl1182.68155MR2541129
  10. [10] A. Glen, J. Justin and G. Pirillo, Characterizations of finite and infinite episturmian words via lexicographic orderings. Eur. J. Combin. 29 (2008) 45–58. Zbl1131.68076MR2368613
  11. [11] A. Glen, F. Levé and G. Richomme, Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. DOI: 10.1016/j.tcs.2008.09.056. Zbl1155.68065MR2473932
  12. [12] E. Godelle, Représentation par des transvections des groupes d’artin-tits. Group Geom. Dyn. 1 (2007) 111–133. Zbl1151.20031MR2319454
  13. [13] J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281–313. Zbl1002.68116MR1896357
  14. [14] J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2003) 385–388. Zbl1060.68094MR1965423
  15. [15] J. Justin and G. Pirillo, Episturmian words: shifts, morphisms and numeration systems. Int. J. Found. Comput. Sci. 15 (2004) 329–348. Zbl1067.68115MR2071462
  16. [16] F. Levé and G. Richomme, Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128–138. Zbl1169.68566MR2132859
  17. [17] F. Levé and G. Richomme, Quasiperiodic episturmian words, in Proceedings of the 6 th International Conference on Words, Marseille, France (2007). Zbl1108.68097
  18. [18] F. Levé and G. Richomme, Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007) 15–25. Zbl1108.68097MR2299022
  19. [19] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 17. Addison-Wesley (1983). Zbl0514.20045MR675953
  20. [20] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90, Cambridge University Press (2002). Zbl1001.68093MR1905123
  21. [21] M. Morse and G. Hedlund, Symbolic Dynamics II. Sturmian trajectories. Amer. J. Math. 61 (1940) 1–42. Zbl0022.34003MR745JFM66.0188.03
  22. [22] G. Paquin and L. Vuillon, A characterization of balanced episturmian sequences. Electron. J. Combin. 14 (2007) 33. Zbl1121.68091MR2302540
  23. [23] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math., Vol. 1794. Springer (2002). Zbl1014.11015MR1970385
  24. [24] G. Rauzy, Nombres algébriques et substitutions. Bull. Soc. Math. France 110 (1982) 147–178. Zbl0522.10032MR667748
  25. [25] G. Rauzy, Mots infinis en arithmétique, in Automata on Infinite words, edited by M. Nivat, D. Perrin. Lect. Notes Comput. Sci., Vol. 192. Springer-Verlag, Berlin (1985). Zbl0613.10044MR814741
  26. [26] G. Richomme, Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302 (2003) 1–34. Zbl1044.68142MR1981940
  27. [27] G. Richomme, Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 761–785. Zbl1101.68075MR2073025
  28. [28] G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393–400. Zbl1118.68111MR2331008
  29. [29] G. Richomme, A local balance property of episturmian words, in Proc. DLT ’07. Lect. Notes Comput. Sci., Vol. 4588. Springer, Berlin (2007) 371–381. Zbl1202.68299MR2380446
  30. [30] R. Risley and L. Zamboni, A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith. 95 (2000) 167–184. Zbl0953.11007MR1785413
  31. [31] P. Séébold, Fibonacci morphisms and Sturmian words. Theoret. Comput. Sci. 88 (1991) 365–384. Zbl0737.68068MR1131075
  32. [32] Z.-X. Wen and Y. Zhang, Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull. 44 (1999) 1755–1760. Zbl1040.20504MR1737516

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.