The Ehrenfeucht–Silberger problem.

Holub, Štěpán and Nowotka, Dirk (2012) The Ehrenfeucht–Silberger problem. Journal of Combinatorial Theory, Series A, 119 (3). pp. 668-682. DOI 10.1016/j.jcta.2011.11.004.

[thumbnail of EhrSil.pdf]
Preview
Text
EhrSil.pdf

Download (338kB) | Preview

Supplementary data:

Abstract

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 t of its longest unbordered factor, such that t is shorter than the period p of w. We show that, if w is of length 7t/3 or more, then t=p which gives the optimal
asymtotic bound.

Document Type: Article
Keywords: combinatorics on words, Ehrenfeucht-Silberger problem, periodicity, unbordered words
Research affiliation: Kiel University
Refereed: Yes
Date Deposited: 21 Jan 2013 11:13
Last Modified: 23 Sep 2019 16:36
URI: https://oceanrep.geomar.de/id/eprint/20160

Actions (login required)

View Item View Item