×

Quasiperiodic Sturmian words and morphisms. (English) Zbl 1108.68097

Summary: We characterize all quasiperiodic Sturmian words: A Sturmian word is not quasiperiodic if and only if it is a Lyndon word. Moreover, we study links between Sturmian morphisms and quasiperiodicity.

MSC:

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

References:

[1] Apostolico, A.; Crochemore, M., String pattern matching for a deluge survival kit, () · Zbl 1021.68029
[2] Apostolico, A.; Ehrenfeucht, A., Efficient detection of quasiperiodicities in strings, Theoretical computer science, 119, 247-265, (1993) · Zbl 0804.68109
[3] Apostolico, A.; Farach, M.; Iliopoulos, C.S., Optimal superprimitivity testing for strings, Information processing letters, 39, 1, 17-20, (1991) · Zbl 0734.68071
[4] Berstel, J., Axel thue’s work on repetitions in words, Publications du lacim, 11, 65-80, (1992)
[5] Berthé, V.; Holton, C.; Zamboni, L.Q., Initial powers of Sturmian words, Acta arithmetica, 122, 315-347, (2006) · Zbl 1117.37005
[6] Ferenczi, S., Complexity of sequences and dynamical systems, Discrete mathematics, 206, 145-154, (1999) · Zbl 0936.37008
[7] Levé, F.; Richomme, G., Quasiperiodic infinite words: some answers, Bulletin of the European association for theoretical computer science, 84, 128-138, (2004) · Zbl 1169.68566
[8] Lothaire, M., ()
[9] Lothaire, M., ()
[10] Lothaire, M., ()
[11] Marcus, S., Bridging two hierarchies of infinite words, Journal of universal computer science, 8, 292-296, (2002) · Zbl 1258.68087
[12] Marcus, S., Quasiperiodic infinite words, Bulletin of the European association for theoretical computer science, 82, 170-174, (2004) · Zbl 1169.68484
[13] 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 9, 2005
[14] Monteil, T.; Marcus, S., Quasiperiodic words: multi-scale case and dynamical properties
[15] Richomme, G., Conjugacy and Episturmian morphisms, Theoretical computer science, 302, 1-34, (2003) · Zbl 1044.68142
[16] Richomme, G., Lyndon morphisms, Bulletin of Belgian mathematical society, 10, 761-785, (2003) · Zbl 1101.68075
[17] Séébold, P., Fibonacci morphisms and Sturmian words, Theoretical computer science, 88, 2, 365-384, (1991) · Zbl 0737.68068
[18] Siromoney, R.; Mathew, L.; Dare, V.R.; Subramanian, K.G., Infinite Lyndon words, Information processing letters, 50, 2, 101-104, (1994) · Zbl 0803.68093
[19] Thue, A., Über die gegenseitige lage gleicher teile gewisser zeichenreihen, Norske videnskapsselskapets skrifter I matematisk-naturvidenskapelig klasse, kristiania, 1, 1-67, (1912) · JFM 44.0462.01
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.