An Inequality for the Number of Periods in a Word
Daniel Gabrić, Narad Rampersad, Jeffrey O. Shallit · International Journal of Foundations of Computer Science · 2021
We prove an inequality for the number of periods in a word [Formula: see text] in terms of the length of [Formula: see text] and its initial critical exponent. Next, we characterize all periods of the length-[Formula: see text] prefix of a characteristic Sturmian word in terms of the lazy Ostrowski representation of [Formula: see text], and use this result to show that our inequality is tight for infinitely many words [Formula: see text]. We propose two related measures of periodicity for infinite words. Finally, we also consider special cases where [Formula: see text] is overlap-free or squarefree.