Let u be a nonempty finite word, a square is a word of the form uu. In this paper, we prove that for a given finite word w, the number of distinct square factors of w is bounded by |w|−|Alph(w)|, where |w| denotes the length of w and |Alph(w)| denotes the number of distinct letters in w. This result answers positively a conjecture stated by Fraenkel and Simpson in 1998 and the d-step conjecture stated by Deza, Franek and Jiang in 2011.
Mathematics Subject Classifications: 68R15, 68R10, 68R05
Keywords: Combinatorics on words, squares, repetition
Cookie SettingseScholarship uses cookies to ensure you have the best experience on our website. You can manage which cookies you want us to use.Our Privacy Statement includes more details on the cookies we use and how we protect your privacy.