ABELIAN PERIODS, PARTIAL WORDS, AND AN EXTENSION OF A THEOREM OF FINE AND WILF

作者：Blanchet Sadri Francine^*; Simmons Sean; Tebbe Amelia; Veprauskas Amy

来源：RAIRO - Theoretical Informatics and Applications, 2013, 47(3): 215-234.

DOI：10.1051/ita/2013034

• Combinatorics on words
• Fine and Wilf's theorem
• partial words
• abelian periods
• periods
• optimal lengths

Recently, Constantinescu and Ilie proved a variant of the well-known periodicity theorem of Fine and Wilf in the case of two relatively prime abelian periods and conjectured a result for the case of two non-relatively prime abelian periods. In this paper, we answer some open problems they suggested. We show that their conjecture is false but we give bounds, that depend on the two abelian periods, such that the conjecture is true for all words having length at least those bounds and show that some of them are optimal. We also extend their study to the context of partial words, giving optimal lengths and describing an algorithm for constructing optimal words.

• 出版日期2013-7