Abstract

Finite words and their overlap properties are considered in this paper. Let w be a finite word of length n with period p and where the maximum length of its unbordered factors equals k. A word is called unbordered if it possesses no proper prefix that is also a suffix of that word. Suppose k<p in w. It is known that n≤2k-2, if w has an unbordered prefix u of length k. We show that, if n=2k-2 then u ends in abⁱ, with two different letters a and b and i≥1, and bⁱ occurs exactly once in w. This answers a conjecture by Harju and the second author of this paper about a structural property of maximum Duval extensions. Moreover, we show here that i≤k/3, which in turn leads us to the solution of a special case of a problem raised by Ehrenfeucht and Silberger in 1979.

Keywords: combinatorics on words, periodicity, borders, Ehrenfeucht-Silberger conjecture

Full paper (preprint): [ps - 302 KB] [ps.gz - 140 KB] [pdf - 148 KB].