Computer Science – Discrete Mathematics
Scientific paper
2003-05-23
Computer Science
Discrete Mathematics
16 pages
Scientific paper
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. We call a word bordered, if it has a proper prefix which is also a suffix of that word. Let f(w) denote the maximum length of all unbordered factors of w, and let p(w) denote the period of w. Clearly, f(w) < p(w)+1. We establish that f(w) = p(w), if w has an unbordered prefix of length f(w) and n > 2f(w)-2. This bound is tight and solves the stronger version of a 21 years old conjecture by Duval. It follows from this result that, in general, n > 3f(w)-3 implies f(w) = p(w) which gives an improved bound for the question asked by Ehrenfeucht and Silberger in 1979.
Harju Tero
Nowotka Dirk
No associations
LandOfFree
Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-133400