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.


68R15 Combinatorics on words
Full Text: DOI


[1] Choffrut, C.; Karhumäki, J., Combinatorics of words, (), 329-438
[2] Lothaire, M., Combinatorics on words, (1983), 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 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. 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.