×

Quasiperiodic and Lyndon episturmian words. (English) Zbl 1155.68065

Summary: Recently the second two authors characterized quasiperiodic Sturmian words, proving that a Sturmian word is non-quasiperiodic if and only if, it is an infinite Lyndon word. Here we extend this study to episturmian words (a natural generalization of Sturmian words) by describing all the quasiperiods of an episturmian word, which yields a characterization of quasiperiodic episturmian words in terms of their directive words. Even further, we establish a complete characterization of all episturmian words that are Lyndon words. Our main results show that, unlike the Sturmian case, there is a much wider class of episturmian words that are non-quasiperiodic, besides those that are infinite Lyndon words. Our key tools are morphisms and directive words, in particular normalized directive words, which we introduced in an earlier paper. Also of importance is the use of return words to characterize quasiperiodic episturmian words, since such a method could be useful in other contexts.

MSC:

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

References:

[1] Allouche, J.-P.; Shallit, J., Automatic sequences: theory, applications, generalizations, (2003), Cambridge University Press · Zbl 1086.11015
[2] Apostolico, A.; Crochemore, M., String pattern matching for a deluge survival kit, () · Zbl 1021.68029
[3] Apostolico, A.; Ehrenfeucht, A., Efficient detection of quasiperiodicities in strings, Theoret. comput. sci., 119, 247-265, (1993) · Zbl 0804.68109
[4] Apostolico, A.; Farach, M.; Iliopoulos, C.S., Optimal superprimitivity testing for strings, Inform. process. lett., 39, 1, 17-20, (1991) · Zbl 0734.68071
[5] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexités \(2 n + 1\), Bull. soc. math. France, 119, 199-215, (1991) · Zbl 0789.28011
[6] Berstel, J., Sturmian and Episturmian words (a survey of some recent results), (), 23-47 · Zbl 1149.68065
[7] Berthé, V.; Holton, C.; Zamboni, L.Q., Initial powers of Sturmian sequences, Acta arith., 122, 315-347, (2006) · Zbl 1117.37005
[8] Borel, J.P.; Laubie, F., Quelques mots sur la droite projective réelle, J. théorie nomb. Bordeaux, 5, 23-51, (1993) · Zbl 0839.11008
[9] Coven, E.M.; Hedlund, G.A., Sequences with minimal block growth, Math. syst. theory, 7, 138-153, (1973) · Zbl 0256.54028
[10] de Luca, A., A combinatorial property of the Fibonacci words, Inform. process. lett., 12, 4, 193-195, (1981) · Zbl 0468.20049
[11] de Luca, A., Sturmian words: structure, combinatorics and their arithmetics, Theoret. comput. sci., 183, 45-82, (1997) · Zbl 0911.68098
[12] Droubay, X.; Justin, J.; Pirillo, G., Episturmian words and some constructions of de luca and Rauzy, Theoret. comput. sci., 255, 1-2, 539-553, (2001) · Zbl 0981.68126
[13] Durand, F., A characterization of substitutive sequences using return words, Discrete math., 179, 89-101, (1998) · Zbl 0895.68087
[14] Ferenczi, S, Complexity of sequences and dynamical systems, Discrete math., 206, 145-154, (1999) · Zbl 0936.37008
[15] A. Glen, Order and quasiperiodicity in episturmian words, in: Proceedings of the 6th International Conference on Words, Marseille, France, September 17-21, 2007, pp. 144-158
[16] Glen, A., A characterization of fine words over a finite alphabet, Theoret. comput. sci., 391, 51-60, (2008) · Zbl 1133.68065
[17] A. Glen, J. Justin, Episturmian words: A survey, preprint, 2007 · Zbl 1182.68155
[18] Glen, A.; Justin, J.; Pirillo, G., Characterizations of finite and infinite Episturmian words via lexicographic orderings, European J. combin., 29, 45-58, (2008) · Zbl 1131.68076
[19] A. Glen, F. Levé, G. Richomme, Directive words of episturmian words: Equivalence and normalization, RAIRO - Theoret. Inform. Appl. 2008 (in press)
[20] Holton, C.; Zamboni, L.Q., Descendants of primitive substitutions, Theory comput. syst., 32, 133-157, (1999) · Zbl 0916.68086
[21] Iliopoulos, C.S.; Mouchard, L., Quasiperiodicity and string covering, Theoret. comput. sci., 218, 1, 205-216, (1999) · Zbl 0916.68121
[22] Justin, J., Episturmian morphisms and a Galois theorem on continued fractions, Theoret. inform. appl., 39, 1, 207-215, (2005) · Zbl 1126.68519
[23] Justin, J.; Pirillo, G., Episturmian words and Episturmian morphisms, Theoret. comput. sci., 276, 1-2, 281-313, (2002) · Zbl 1002.68116
[24] Justin, J.; Pirillo, G., On a characteristic property of arnoux-Rauzy sequences, Theoret. inform. appl., 36, 4, 385-388, (2003) · Zbl 1060.68094
[25] Justin, J.; Pirillo, G., Episturmian words: shifts, morphisms and numeration systems, Internat. J. found. comput. sci., 15, 2, 329-348, (2004) · Zbl 1067.68115
[26] Justin, J.; Vuillon, L., Return words in sturmian and Episturmian words, Theoret. inform. appl., 34, 343-356, (2000) · Zbl 0987.68055
[27] Levé, F.; Richomme, G., Quasiperiodic infinite words: some answers, Bull. eur. assoc. theoret. comput. sci., 84, 128-138, (2004) · Zbl 1169.68566
[28] F. Levé, G. Richomme, Quasiperiodic episturmian words, in: Proceedings of the 6th International Conference on Words, Marseille, France, September 17-21, 2007, pp. 201-211
[29] Levé, F.; Richomme, G., Quasiperiodic Sturmian words and morphisms, Theoret. comput. sci., 372, 15-25, (2007) · Zbl 1108.68097
[30] Lothaire, M., ()
[31] Lothaire, M., ()
[32] Marcus, S., Bridging two hierarchies of infinite words, J. ucs, 8, 292-296, (2002) · Zbl 1258.68087
[33] Marcus, S., Quasiperiodic infinite words, Bull. eur. assoc. theoret. comput. sci., 82, 170-174, (2004) · Zbl 1169.68484
[34] Melançon, G., Lyndon factorization of Sturmian words, Discrete math., 210, 137-149, (2000) · Zbl 0946.68113
[35] T. Monteil, Illumination dans les billards polygonaux et dynamique symbolique, Ph.D. Thesis, Université de la Méditerranée, Faculté des Sciences de Luminy, December 2005
[36] Morse, M.; Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories, Amer. J. math., 61, 1-42, (1940) · JFM 66.0188.03
[37] Paquin, G.; Vuillon, L., A characterization of balanced Episturmian sequences, Electron. J. combin., 14, (2007), #R33, pp. 12 · Zbl 1121.68091
[38] Pytheas Fogg, N., ()
[39] Rauzy, G., Nombres algébriques et substitutions, Bull. soc. math. France, 110, 147-178, (1982) · Zbl 0522.10032
[40] Rauzy, G., Mots infinis en arithmétique, (), 165-171 · Zbl 0613.10044
[41] Richomme, G., Conjugacy and Episturmian morphisms, Theoret. comput. sci., 302, 1-3, 1-34, (2003) · Zbl 1044.68142
[42] Richomme, G., Lyndon morphisms, Bull. belg. math. soc. Simon stevin, 10, 761-785, (2003) · Zbl 1101.68075
[43] Richomme, G., Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words, Theoret. comput. sci., 380, 3, 393-400, (2007) · Zbl 1118.68111
[44] Richomme, G., A local balance property of Episturmian words, (), 371-381 · Zbl 1202.68299
[45] Richomme, G., On morphisms preserving infinite Lyndon words, Discrete math. theoret. comput. sci., 9, 89-108, (2007) · Zbl 1152.68490
[46] Risley, R.N.; Zamboni, L.Q, A generalization of Sturmian sequences: combinatorial structure and transcendence, Acta arith., 95, 167-184, (2000) · Zbl 0953.11007
[47] Séébold, P., Fibonacci morphisms and Sturmian words, Theoret. comput. sci., 88, 2, 365-384, (1991) · Zbl 0737.68068
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.