Holub, Štěpán and Nowotka, Dirk (2009) The Ehrenfeucht-Silberger Problem. [Paper] In: International Colloquium on Automata, Languages and Programming (ICALP). , 5 - 12 Jul 2009, Rhodos, Greece . Automata, Languages and Programming. ; pp. 537-548 . DOI 10.1007/978-3-642-02927-1_45. Lecture Notes in Computer Science .

Preview

Text TheEhrSilProblem.pdf Download (208kB) | Preview

Abstract

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 t of its longest unbordered factor still allowing that t is shorter than the period p of w. We show that if w is longer than 7(t-1)/3 then t=p which gives the optimal asymtotic bound.

Actions (login required)

View Item