Directive words of episturmian words: equivalences and normalization. (English) Zbl 1166.68034

Summary: 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.


68R15 Combinatorics on words
Full Text: DOI arXiv EuDML Link


[1] J.-P. Allouche and J. Shallit, Automatic sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). · Zbl 1086.11015
[2] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexités 2 n + 1 . Bull. Soc. Math. France119 (1991) 199-215. · Zbl 0789.28011
[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 1149.68065
[4] V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Arith.122 (2006) 315-347. Zbl1117.37005 · Zbl 1117.37005
[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. · Zbl 0981.68126
[6] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145-154. Zbl0936.37008 · Zbl 0936.37008
[7] A. Glen, On Sturmian and episturmian words, and related topics. Ph.D. thesis, The University of Adelaide, Australia (2006). · Zbl 1102.68516
[8] A. Glen, A characterization of fine words over a finite alphabet. Theoret. Comput. Sci.391 (2008) 51-60. · Zbl 1133.68065
[9] A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl. (submitted). e-print arxiv:0801.1655 (2007).
[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. · Zbl 1131.68076
[11] A. Glen, F. Levé and G. Richomme, Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. DOI: . DOI10.1016/j.tcs.2008.09.056 · Zbl 1155.68065
[12] E. Godelle, Représentation par des transvections des groupes d’artin-tits. Group Geom. Dyn.1 (2007) 111-133. · Zbl 1151.20031
[13] J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci.276 (2002) 281-313. · Zbl 1002.68116
[14] J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl.36 (2003) 385-388. · Zbl 1060.68094
[15] J. Justin and G. Pirillo, Episturmian words: shifts, morphisms and numeration systems. Int. J. Found. Comput. Sci.15 (2004) 329-348. · Zbl 1067.68115
[16] F. Levé and G. Richomme, Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci.84 (2004) 128-138. Zbl1169.68566 · Zbl 1169.68566
[17] F. Levé and G. Richomme, Quasiperiodic episturmian words, in Proceedings of the 6th International Conference on Words, Marseille, France (2007). · Zbl 1202.68299
[18] F. Levé and G. Richomme, Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci.372 (2007) 15-25. Zbl1108.68097 · Zbl 1108.68097
[19] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 17. Addison-Wesley (1983). · Zbl 0514.20045
[20] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90, Cambridge University Press (2002). Zbl1001.68093 · Zbl 1001.68093
[21] M. Morse and G. Hedlund, Symbolic Dynamics II. Sturmian trajectories. Amer. J. Math.61 (1940) 1-42. Zbl0022.34003 · Zbl 0022.34003
[22] G. Paquin and L. Vuillon, A characterization of balanced episturmian sequences. Electron. J. Combin.14 (2007) 33. Zbl1121.68091 · Zbl 1121.68091
[23] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math., Vol. 1794. Springer (2002). · Zbl 1014.11015
[24] G. Rauzy, Nombres algébriques et substitutions. Bull. Soc. Math. France110 (1982) 147-178. · Zbl 0522.10032
[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.10044 · Zbl 0613.10044
[26] G. Richomme, Conjugacy and episturmian morphisms. Theoret. Comput. Sci.302 (2003) 1-34. · Zbl 1044.68142
[27] G. Richomme, Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin10 (2003) 761-785. · Zbl 1101.68075
[28] G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci.380 (2007) 393-400. · Zbl 1118.68111
[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. · Zbl 1202.68299
[30] R. Risley and L. Zamboni, A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith.95 (2000) 167-184. · Zbl 0953.11007
[31] P. Séébold, Fibonacci morphisms and Sturmian words. Theoret. Comput. Sci.88 (1991) 365-384. · Zbl 0737.68068
[32] Z.-X. Wen and Y. Zhang, Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull.44 (1999) 1755-1760. · Zbl 1040.20504
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.