Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T11:51:27.903Z Has data issue: false hasContentIssue false
  • English
  • Français

Directive words of episturmian words: equivalences and normalization

Published online by Cambridge University Press:  22 November 2008

Amy Glen ,
Florence Levé  and
Gwénaël Richomme
Amy Glen
Affiliation:
LaCIM, Université du Québec à Montréal, C.P. 8888, succursale Centre-ville, Montréal, Québec, H3C 3P8, Canada The Mathematics Institute, Reykjavík University, Kringlan 1, IS-103 Reykjavík, Iceland; [email protected]
Florence Levé
Affiliation:
Université de Picardie Jules Verne, Laboratoire MIS (Modélisation, Information, Systèmes), 33 rue Saint Leu, 80039 Amiens Cedex 1, France; [email protected]; [email protected]
Gwénaël Richomme
Affiliation:
Université de Picardie Jules Verne, Laboratoire MIS (Modélisation, Information, Systèmes), 33 rue Saint Leu, 80039 Amiens Cedex 1, France; [email protected]; [email protected]
Get access

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.

Keywords

Episturmian wordSturmian wordArnoux-Rauzy sequenceepisturmian morphismdirective word.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 2 , April 2009 , pp. 299 - 319
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J.-P. Allouche and J. Shallit, Automatic sequences: Theory, Applications, Generalizations. Cambridge University Press (2003).
Arnoux, P. and Rauzy, G., Représentation géométrique de suites de complexités $2n+1$ . Bull. Soc. Math. France 119 (1991) 199–215. CrossRef
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).
Berthé, V., Holton, C. and Zamboni, L.Q., Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315–347. CrossRef
Droubay, X., Justin, J. and Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539–553. CrossRef
Ferenczi, S., Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145–154. CrossRef
A. Glen, On Sturmian and episturmian words, and related topics. Ph.D. thesis, The University of Adelaide, Australia (2006).
Glen, A., A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. 391 (2008) 51–60. CrossRef
A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl. (submitted). e-print arxiv:0801.1655 (2007).
Glen, A., Justin, J. and Pirillo, G., Characterizations of finite and infinite episturmian words via lexicographic orderings. Eur. J. Combin. 29 (2008) 45–58. CrossRef
A. Glen, F. Levé and G. Richomme, Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. DOI: 10.1016/j.tcs.2008.09.056.
Godelle, E., Représentation par des transvections des groupes d'artin-tits. Group Geom. Dyn. 1 (2007) 111–133. CrossRef
Justin, J. and Pirillo, G., Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281–313. CrossRef
Justin, J. and Pirillo, G., On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2003) 385–388. CrossRef
Justin, J. and Pirillo, G., Episturmian words: shifts, morphisms and numeration systems. Int. J. Found. Comput. Sci. 15 (2004) 329–348. CrossRef
Levé, F. and Richomme, G., Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128–138.
F. Levé and G. Richomme, Quasiperiodic episturmian words, in Proceedings of the 6th International Conference on Words, Marseille, France (2007).
Levé, F. and Richomme, G., Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007) 15–25. CrossRef
M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 17. Addison-Wesley (1983).
M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90, Cambridge University Press (2002).
M. Morse and G. Hedlund, Symbolic Dynamics II. Sturmian trajectories. Amer. J. Math. 61 (1940) 1–42.
Paquin, G. and Vuillon, L., A characterization of balanced episturmian sequences. Electron. J. Combin. 14 (2007) 33.
N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math., Vol. 1794. Springer (2002).
Rauzy, G., Nombres algébriques et substitutions. Bull. Soc. Math. France 110 (1982) 147–178. CrossRef
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).
Richomme, G., Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302 (2003) 1–34. CrossRef
Richomme, G., Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 761–785.
Richomme, G., Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393–400. CrossRef
G. Richomme, A local balance property of episturmian words, in Proc. DLT '07. Lect. Notes Comput. Sci., Vol. 4588. Springer, Berlin (2007) 371–381.
Risley, R. and Zamboni, L., A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith. 95 (2000) 167–184.
Séébold, P., Fibonacci morphisms and Sturmian words. Theoret. Comput. Sci. 88 (1991) 365–384. CrossRef
Wen, Z.-X. and Zhang, Y., Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull. 44 (1999) 1755–1760. CrossRef