×

Locally periodic versus globally periodic infinite words. (English) Zbl 1011.68070

Summary: We call a one-way infinite word \(w\) over a finite alphabet \((\rho,l)\)-repetitive if all long enough prefixes of \(w\) contain as a suffix a \(\rho\)th power (or more generally a repetition of order \(\rho\)) of a word of length at most \(l\). We show that each (2,4)-repetitive word is ultimately periodic, as well as that there exist continuum many, and hence also nonultimately periodic, (2,5)-repetitive words. Further, we characterize nonultimately periodic (2,5)-repetitive words both structurally and algebraically.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Choffrut, C.; Karhumäki, J., Combinatorics of words, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, 1 (1995), Springer: Springer Berlin), 329-438
[2] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading · Zbl 0514.20045
[3] Mignosi, F.; Pirillo, G., Repetitions in the Fibonacci infinite word, RAIRO Theor. Inform. Appl., 26, 199-204 (1992) · Zbl 0761.68078
[4] Mignosi, F.; Restivo, A.; Salemi, S., A periodicity theorem on words and applications, MFCS’95, 969 (1995), Springer: Springer Berlin, p. 337-348 · Zbl 1193.68202
[5] Mignosi, F.; Restivo, A.; Salemi, S., Periodicity and golden ratio, Theoret. Comput. Sci., 204, 153-167 (1998) · Zbl 0913.68162
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.