×

Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. (English) Zbl 1118.68111

Summary: Using the notions of conjugacy of morphisms and of morphisms preserving Lyndon words, we answer a question of G. Melançon. We characterize cases where the sequence of Lyndon words in the Lyndon factorization of a standard Sturmian word is morphic. In each possible case, the corresponding morphism is given.

MSC:

68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI HAL

References:

[1] J. Berstel, P. Séébold, Sturmian words, chapter 2 in [9] · Zbl 1096.68689
[2] Berthé, V.; Holton, C.; Zamboni, L.Q., Initial powers of Sturmian sequences, Acta arithmetica, 122, 315-347, (2006) · Zbl 1117.37005
[3] Borel, J.P.; Laubie, F., Quelques mots sur la droite projective réelle, Journal de théorie des nombres de Bordeaux, 5, 23-51, (1993) · Zbl 0839.11008
[4] Chen, K.T.; Fox, R.H.; Lyndon, R.C., Free differential calculus IV — the quotient groups of the lower central series, Annals of mathematics 68, 68, 81-95, (1958) · Zbl 0142.22304
[5] Ido, A.; Melançon, G., Lyndon factorization of the thue – morse word and its relatives, Discrete mathematics and theoretical computer science, 1, 43-52, (1997) · Zbl 0942.11022
[6] Justin, J.; Pirillo, G., Episturmian words and Episturmian morphisms, Theoretical computer science, 276, 1-2, 281-313, (2002) · Zbl 1002.68116
[7] Justin, J.; Pirillo, G., On a characteristic property of arnoux – rauzy sequences, RAIRO theoretical informatics and applications, 36, 385-388, (2002) · Zbl 1060.68094
[8] Lothaire, M., (), Reprinted in 1997 by Cambridge University Press in the Cambridge Mathematical Library, Cambridge, UK, 1997
[9] Lothaire, M., ()
[10] Lothaire, M., ()
[11] Melançon, G., Lyndon factorization of infinite words, (), 147-154 · Zbl 1379.68266
[12] Melançon, G., Lyndon factorization of Sturmian words, Discrete mathematics, 210, 137-149, (2000) · Zbl 0946.68113
[13] Richomme, G., Conjugacy and Episturmian morphisms, Theoretical computer science, 302, 1-34, (2003) · Zbl 1044.68142
[14] Richomme, G., Lyndon morphisms, Bulletin of the Belgian mathematical society, 10, 761-785, (2003) · Zbl 1101.68075
[15] G. Richomme, On morphisms preserving infinite Lyndon words, Discrete Mathematics and Theoretical Computer Science (in press). An extended abstract appeared in the proceedings of the conference “Journées Montoises d’Informatique Théorique”, Liège, Belgium, 2004 (Prépublication 04.006, Institut de Mathématique, Université de Lié ge), pp. 325-333
[16] Séébold, P., Fibonacci morphisms and Sturmian words, Theoretical computer science, 88, 365-384, (1991) · Zbl 0737.68068
[17] Séébold, P., On the conjugation of standard morphisms, Theoretical computer science, 195, 91-109, (1998) · Zbl 0981.68104
[18] Séébold, P., Lyndon factorization of the prouhet words, Theoretical computer science, 307, 179-197, (2003) · Zbl 1058.68089
[19] Siromoney, R.; Mathew, L.; Dare, V.R.; Subramanian, K.G., Infinite Lyndon words, Information processing letters, 50, 101-104, (1994) · Zbl 0803.68093
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.