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 - Informatique Théorique et Applications, Tome 47 (2013), p. 215-234 / Harvested from Numdam

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.

Publié le : 2013-01-01
DOI : https://doi.org/10.1051/ita/2013034
Classification:  68R15,  68Q25
@article{ITA_2013__47_3_215_0,
     author = {Blanchet-Sadri, Francine and Simmons, Sean and Tebbe, Amelia and Veprauskas, Amy},
     title = {Abelian periods, partial words, and an extension of a theorem of Fine and Wilf},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {47},
     year = {2013},
     pages = {215-234},
     doi = {10.1051/ita/2013034},
     mrnumber = {3103125},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2013__47_3_215_0}
}
Blanchet-Sadri, Francine; Simmons, Sean; Tebbe, Amelia; Veprauskas, Amy. Abelian periods, partial words, and an extension of a theorem of Fine and Wilf. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) pp. 215-234. doi : 10.1051/ita/2013034. http://gdmltest.u-ga.fr/item/ITA_2013__47_3_215_0/

[1] S.V. Avgustinovich, A. Glen, B.V. Halldórsson and S. Kitaev, On shortest crucial words avoiding abelian powers. Discrete Appl. Math. 158 (2010) 605-607. | MR 2594475 | Zbl 1226.68074

[2] S.V. Avgustinovich, J. Karhumäki and S. Puzynina, On abelian versions of the critical factorization theorem. In JM 2010, 13ièmes Journées Montoises d'Informatique Théorique, Amiens, France (2010). | Numdam | Zbl 1247.68200

[3] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135-141. | MR 1687780 | Zbl 0916.68120

[4] F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton, FL (2008). | MR 2384993 | Zbl 1180.68205

[5] F. Blanchet-Sadri, J.I. Kim, R. Mercaş, W. Severa, S. Simmons and D. Xu, Avoiding abelian squares in partial words. J. Combin. Theory Ser. A 119 (2012) 257-270. | MR 2844095 | Zbl 1233.68183

[6] F. Blanchet-Sadri, T. Mandel and G. Sisodia, Periods in partial words: An algorithm. J. Discrete Algorithms 16 (2012) 113-128. | MR 2960349 | Zbl 1279.68279

[7] F. Blanchet-Sadri, T. Oey and T. Rankin, Fine and Wilf's theorem for partial words with arbitrarily many weak periods. Internat. J. Foundations Comput. Sci. 21 (2010) 705-722. | MR 2728320 | Zbl 1213.68354

[8] F. Blanchet-Sadri, S. Simmons and D. Xu, Abelian repetitions in partial words. Adv. Appl. Math. 48 (2012) 194-214. | MR 2845515 | Zbl 1231.68187

[9] F. Blanchet-Sadri, A. Tebbe and A. Veprauskas, Fine and Wilf's theorem for abelian periods in partial words. In JM 2010, 13ièmes Journées Montoises d'Informatique Théorique, Amiens, France (2010).

[10] M.G. Castelli, F. Mignosi and A. Restivo, Fine and Wilf's theorem for three periods and a generalization of Sturmian words. Theoret. Comput. Sci. 218 (1999) 83-94. | MR 1687764 | Zbl 0916.68114

[11] C. Choffrut and J. Karhumäki, Combinatorics of Words. In Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin Vol. 1 (1997) 329-438. | MR 1469998 | Zbl 0866.68057

[12] S. Constantinescu and L. Ilie, Generalised Fine and Wilf's theorem for arbitrary number of periods. Theor. Comput. Sci. 339 (2005) 49-60. | MR 2142073 | Zbl 1127.68074

[13] S. Constantinescu and L. Ilie, Fine and Wilf's theorem for abelian periods. Bull. Eur. Assoc. Theor. Comput. Sci. 89 (2006) 167-170. | MR 2267841 | Zbl 1169.68561

[14] L.J. Cummings and W.F. Smyth, Weak repetitions in strings. J. Combin. Math. Combin. Comput. 24 (1997) 33-48. | MR 1451514 | Zbl 0882.68111

[15] J. Currie and A. Aberkane, A cyclic binary morphism avoiding abelian fourth powers. Theoret. Comput. Sci. 410 (2009) 44-52. | MR 2488310 | Zbl 1161.68044

[16] M. Domaratzki and N. Rampersad, Abelian primitive words. In DLT 2011, 15th International Conference on Developments in Language Theory, Milano, Italy, Lect. Notes Comput. Sci. Vol. 6795 edited by G. Mauri and A. Leporati. Springer-Verlag, Berlin, Heidelberg (2011) 204-215. | MR 2862727 | Zbl 1221.68125

[17] G. Fici, T. Lecroq, A. Lefebvre and E. Prieur-Gaston, Computing abelian periods in words. PSC 2011, Prague Stringology Conference, Prague, Czech Republic, (2011) 184-196.

[18] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | MR 174934 | Zbl 0131.30203

[19] V. Halava, T. Harju and T. Kärki, Interaction properties of relational periods. Discrete Math. Theoret. Comput. Sci. 10 (2008) 87-112. | MR 2393230 | Zbl 1139.68045

[20] J. Justin, On a paper by Castelli, Mignosi, Restivo. Theoret. Inform. Appl. 34 (2000) 373-377. | Numdam | MR 1829233 | Zbl 0987.68056

[21] V. Keränen, Abelian squares are avoidable on 4 letters. In ICALP 1992, 19th International Colloquium on Automata, Languages and Programming, Lect. Notes Comput. Sci. Vol. 623 edited by W. Kuich. Springer-Verlag, Berlin (1992) 241-52. | MR 1250629

[22] A.V. Samsonov and A.M. Shur, On abelian repetition threshold. In JM 2010, 13ièmes Journées Montoises d'Informatique Théorique, Amiens, France (2010). | Numdam | Zbl 1279.68240

[23] A.M. Shur and Y.V. Gamzova, Partial words and the interaction property of periods. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 68 (2004) 191-214. | MR 2058005 | Zbl 1088.68147

[24] A.M. Shur and Y.V. Konovalova, On the periods of partial words. In MFCS 2001, 26th International Symposium on Mathematical Foundations of Computer Science, Lect. Notes Comput. Sci. Vol. 2136 edited by J. Sgall, A. Pultr and P. Kolman. London, UK, Springer-Verlag. (2001) 657-665. | MR 1907051 | Zbl 0999.68165

[25] W. F. Smyth and S. Wang, A new approach to the periodicity lemma on strings with holes. Theoret. Comput. Sci. 410 (2009) 4295-4302. | MR 2553581 | Zbl 1181.68181

[26] R. Tijdeman and L. Zamboni, Fine and Wilf words for any periods. Indagationes Math. 14 (2003) 135-147. | MR 2015604 | Zbl 1091.68088