Tero Harju and Dirk Nowotka
Periodicity and Unbordered Words


In V. Diekert and M. Habib (eds), STACS (Montpellier, 2004), volume 2996 of Lecture Notes in Computer Science, pages 294-304, Springer-Verlag, Berlin, 2004.

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 μ(w) denote the maximum length of its unbordered factors, and let (w) denote the period of w. Clearly, μ(w) ≤ (w).

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

Keywords: combinatorics on words, Duval's conjecture

Full paper: [ps - 723 KB] [ps.gz - 121 KB] [pdf - 180 KB].