Abstrakt
We consider repetitions in words and solve a longstanding open problem about the relation between the period of a word and the length of its longest unbordered factor (where factor means uninterrupted subword). A word u is called bordered if there exists a proper prefix that is also a suffix of u, otherwise it is called unbordered.
In 1979 Ehrenfeucht and Silberger raised the following problem: What is the maximum length of a word w, w.r.t. the length tau of its longest unbordered factor, such that tau is shorter than the period pi of w. We show that, if w is of length 7/3 tau or more, then tau = pi which gives the optimal asymptotic bound. 2011 Elsevier Inc.
All rights reserved.