About Duval’s Conjecture

  • T. Harju
  • D. Nowotka
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


A word is called unbordered if it has no proper prefix which is also a suffix of that word. Let µ(w) denote the length of the longest unbordered factor of a word w. Let a word where the longest unbordered prefix equal to µ(w) be called Duval extension. A Duval extension is called trivial, if its longest unbordered factor is of the length of the period of that Duval extension. In 1982 it was shown by Duval that every Duval extension w longer than 3µ(w) − 4 is trivial. We improve that bound to 5µ(w)/2−1 in this paper, and with that, move closer to the bound 2µ(w) conjectured by Duval. Our proof also contains a natural application of the Critical Factorization Theorem.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    R. Assous and M. Pouzet. Une caractérisation des mots périodiques. Discrete Math., 25(1):1–5, 1979.zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Y. Césari and M. Vincent. Une caractérisation des mots périodiques. C. R. Acad. Sci. Paris Sér. A, 286:1175–1177, 1978.zbMATHGoogle Scholar
  3. 3.
    J.-P. Duval. Périodes et répétitions des mots de monoïde libre. Theoret. Comput. Sci., 9(1):17–26, 1979.zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    J.-P. Duval. Relationship between the period of a finite word and the length of its unbordered segments. Discrete Math., 40(1):31–44, 1982.zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    A. Ehrenfeucht and D. M. Silberger. Periodicity and unbordered segments of words. Discrete Math., 26(2):101–109, 1979.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    T. Harju and D. Nowotka. Density of critical factorizations. Theor. Inform. Appl., 36(3):315–327, 2002.zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    T. Harju and D. Nowotka. Duval’s conjecture and Lyndon words. submitted to Discrete Math., 2002.Google Scholar
  8. 8.
    D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323–350, 1977.zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics. Addison-Wesley, Reading, Massachusetts, 1983.zbMATHGoogle Scholar
  10. 10.
    M. Lothaire. Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, United Kingdom, 2002.zbMATHGoogle Scholar
  11. 11.
    F. Mignosi and L. Q. Zamboni. A note on a conjecture of Duval and Sturmian words. Theor. Inform. Appl., 36(1):1–3, 2002.zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • T. Harju
    • 1
  • D. Nowotka
    • 1
  1. 1.Turku Centre for Computer Science (TUCS), Department of MathematicsUniversity of TurkuFinland

Personalised recommendations