Harju, Tero and Nowotka, Dirk (2004) Periodicity and Unbordered Words. [Paper] In: Symposium on Theoretical Aspects of Computer Science (STACS). , 25 - 27 Mar 2004, Montpellier, France . STACS 2004. ; pp. 294-304 . DOI 10.1007/978-3-540-24749-4_26. Lecture Notes in Computer Science .

Preview

Text DuvalConjecture.pdf Download (184kB) | Preview

Abstract

The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this paper.

Consider a finite word w of length n. Let u(w) denote the maximum length of its unbordered factors, and let p(w) denote the period of w. Clearly, u(w) <= p(w).

We establish that u(w) = p(w), if w has an unbordered prefix of length u(w) and n >= 2u(w)-1. This bound is tight and solves a 21 year old conjecture by Duval. It follows from this result that, in general, n ≥ 3u(w) implies u(w) = p(w) which gives an improved bound for the question asked by Ehrenfeucht and Silberger in 1979.

Actions (login required)

View Item