Directive words of episturmian words : equivalences and normalization

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 299-319.

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.

Classification : 68R15
Mots clés : episturmian word, sturmian word, Arnoux-Rauzy sequence, episturmian morphism, directive word

[1] J.-P. Allouche and J. Shallit, Automatic sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). | MR | Zbl

[2] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexités $2n+1$. Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR | Zbl

[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). | Zbl

[4] V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315-347. | MR | Zbl

[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. | MR | Zbl

[6] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR | Zbl

[7] A. Glen, On Sturmian and episturmian words, and related topics. Ph.D. thesis, The University of Adelaide, Australia (2006). | Zbl

[8] A. Glen, A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. 391 (2008) 51-60. | MR | Zbl

[9] A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl. (submitted). e-print arxiv:0801.1655 (2007). | Numdam | MR

[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. | MR | Zbl

[11] A. Glen, F. Levé and G. Richomme, Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. DOI: 10.1016/j.tcs.2008.09.056. | MR | Zbl

[12] E. Godelle, Représentation par des transvections des groupes d'artin-tits. Group Geom. Dyn. 1 (2007) 111-133. | MR | Zbl

[13] J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | MR | Zbl

[14] J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2003) 385-388. | Numdam | MR | Zbl

[15] J. Justin and G. Pirillo, Episturmian words: shifts, morphisms and numeration systems. Int. J. Found. Comput. Sci. 15 (2004) 329-348. | MR | Zbl

[16] F. Levé and G. Richomme, Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128-138. | MR | Zbl

[17] F. Levé and G. Richomme, Quasiperiodic episturmian words2007).

[18] F. Levé and G. Richomme, Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007) 15-25. | MR | Zbl

[19] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 17. Addison-Wesley (1983). | MR | Zbl

[20] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90, Cambridge University Press (2002). | MR | Zbl

[21] M. Morse and G. Hedlund, Symbolic Dynamics II. Sturmian trajectories. Amer. J. Math. 61 (1940) 1-42. | JFM | MR

[22] G. Paquin and L. Vuillon, A characterization of balanced episturmian sequences. Electron. J. Combin. 14 (2007) 33. | MR | Zbl

[23] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math., Vol. 1794. Springer (2002). | MR | Zbl

[24] G. Rauzy, Nombres algébriques et substitutions. Bull. Soc. Math. France 110 (1982) 147-178. | Numdam | MR | Zbl

[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). | MR | Zbl

[26] G. Richomme, Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302 (2003) 1-34. | MR | Zbl

[27] G. Richomme, Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 761-785. | MR | Zbl

[28] G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393-400. | MR | Zbl

[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. | MR

[30] R. Risley and L. Zamboni, A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith. 95 (2000) 167-184. | MR | Zbl

[31] P. Séébold, Fibonacci morphisms and Sturmian words. Theoret. Comput. Sci. 88 (1991) 365-384. | MR | Zbl

[32] Z.-X. Wen and Y. Zhang, Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull. 44 (1999) 1755-1760. | MR | Zbl