Holub, Štěpán and Nowotka, Dirk (2008) On the Relation between Periodicity and Unbordered Factors of Finite Words. [Paper] In: Developments in Language Theory (DLT). , 16 - 19 Sep 2008, Kyoto, Japan . Developments in Language Theory. ; pp. 408-418 . DOI 10.1007/978-3-540-85780-8_32. Lecture Notes in Computer Science .

Preview

Text OnTheEhrSilConjecture.pdf Download (151kB) | Preview

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-1, if w has an unbordered prefix u of length k. We show that, if n=2k-2 then u ends in abi, with two different letters a and b and i>0, and bi 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.

Actions (login required)

View Item