Štěpán Holub and Dirk Nowotka
The Ehrenfeucht Silberger Problem
Automata, Languages and Programming (ICALP), Rhodes, 2009, volume 5555 of Lecture Notes in Computer Science, pages 537-548, Springer-Verlag, Berlin, 2009.
We consider repetitions in words and solve a longstanding open problem about the relation between the period and the length of its longest unbordered factor. 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 τ of its longest unbordered factor still allowing that τ is shorter than the period π of w. We show that if w is longer than 7(τ-1)/3 then τ=π which gives the optimal asymtotic bound.
Keywords: combinatorics on words, periodicity, borders, Ehrenfeucht-Silberger problem