OceanRep
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.
Preview |
Text
EhrSil.pdf Download (338kB) | Preview |
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 |
Copyright 2023 | GEOMAR Helmholtz-Zentrum für Ozeanforschung Kiel | All rights reserved
Questions, comments and suggestions regarding the GEOMAR repository are welcomed
at bibliotheksleitung@geomar.de !