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.
@article{ITA_2009__43_2_299_0,
author = {Glen, Amy and Lev\'e, Florence and Richomme, Gw\'ena\"el},
title = {Directive words of episturmian words : equivalences and normalization},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {43},
year = {2009},
pages = {299-319},
doi = {10.1051/ita:2008029},
mrnumber = {2512261},
zbl = {1166.68034},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2009__43_2_299_0}
}
Glen, Amy; Levé, Florence; Richomme, Gwénaël. Directive words of episturmian words : equivalences and normalization. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 299-319. doi : 10.1051/ita:2008029. http://gdmltest.u-ga.fr/item/ITA_2009__43_2_299_0/
[1] and , Automatic sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). | MR 1997038 | Zbl 1086.11015
[2] and , Représentation géométrique de suites de complexités . Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR 1116845 | Zbl 0789.28011
[3] , 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] , and , Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315-347. | MR 2234421 | Zbl 1117.37005
[5] , and , Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | MR 1819089 | Zbl 0981.68126
[6] , Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR 1665394 | Zbl 0936.37008
[7] , On Sturmian and episturmian words, and related topics. Ph.D. thesis, The University of Adelaide, Australia (2006). | Zbl 1102.68516
[8] , A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. 391 (2008) 51-60. | MR 2381351 | Zbl 1133.68065
[9] and , Episturmian words: a survey. RAIRO-Theor. Inf. Appl. (submitted). e-print arxiv:0801.1655 (2007). | Numdam | MR 2541129 | Zbl pre05578831
[10] , and , Characterizations of finite and infinite episturmian words via lexicographic orderings. Eur. J. Combin. 29 (2008) 45-58. | MR 2368613 | Zbl 1131.68076
[11] , and , Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. DOI: 10.1016/j.tcs.2008.09.056. | MR 2473932 | Zbl 1155.68065
[12] , Représentation par des transvections des groupes d'artin-tits. Group Geom. Dyn. 1 (2007) 111-133. | MR 2319454 | Zbl 1151.20031
[13] and , Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | MR 1896357 | Zbl 1002.68116
[14] and , On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2003) 385-388. | Numdam | MR 1965423 | Zbl 1060.68094
[15] and , Episturmian words: shifts, morphisms and numeration systems. Int. J. Found. Comput. Sci. 15 (2004) 329-348. | MR 2071462 | Zbl 1067.68115
[16] and , Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128-138. | MR 2132859 | Zbl 1169.68566
[17] and , Quasiperiodic episturmian words2007).
[18] and , Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007) 15-25. | MR 2299022 | Zbl 1108.68097
[19] , Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 17. Addison-Wesley (1983). | MR 675953 | Zbl 0514.20045
[20] , Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90, Cambridge University Press (2002). | MR 1905123 | Zbl 1001.68093
[21] and , Symbolic Dynamics II. Sturmian trajectories. Amer. J. Math. 61 (1940) 1-42. | JFM 66.0188.03 | MR 745
[22] and , A characterization of balanced episturmian sequences. Electron. J. Combin. 14 (2007) 33. | MR 2302540 | Zbl 1121.68091
[23] , Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math., Vol. 1794. Springer (2002). | MR 1970385 | Zbl 1014.11015
[24] , Nombres algébriques et substitutions. Bull. Soc. Math. France 110 (1982) 147-178. | Numdam | MR 667748 | Zbl 0522.10032
[25] , 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 814741 | Zbl 0613.10044
[26] , Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302 (2003) 1-34. | MR 1981940 | Zbl 1044.68142
[27] , Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 761-785. | MR 2073025 | Zbl 1101.68075
[28] , Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393-400. | MR 2331008 | Zbl 1118.68111
[29] , A local balance property of episturmian words, in Proc. DLT '07. Lect. Notes Comput. Sci., Vol. 4588. Springer, Berlin (2007) 371-381. | MR 2380446 | Zbl pre05215389
[30] and , A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith. 95 (2000) 167-184. | MR 1785413 | Zbl 0953.11007
[31] , Fibonacci morphisms and Sturmian words. Theoret. Comput. Sci. 88 (1991) 365-384. | MR 1131075 | Zbl 0737.68068
[32] and , Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull. 44 (1999) 1755-1760. | MR 1737516 | Zbl 1040.20504