Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture
| dc.creator | Harju, Tero | |
| dc.creator | Nowotka, Dirk | |
| dc.date | 2003-05-23 | |
| dc.date | 2003-05-25 | |
| dc.date.accessioned | 2026-07-07T03:19:43Z | |
| dc.date.available | 2026-07-07T03:19:43Z | |
| dc.description | 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. | |
| dc.description | 16 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0305039 | |
| dc.identifier | http://arxiv.org/abs/cs/0305039 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31573 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.4.m | |
| dc.title | Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture | |
| dc.type | text |