Abelian periods, partial words, and an extension of a theorem of Fine and Wilf

Francine Blanchet-Sadri; Sean Simmons; Amelia Tebbe; Amy Veprauskas

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 3, page 215-234
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Blanchet-Sadri, Francine, et al. "Abelian periods, partial words, and an extension of a theorem of Fine and Wilf." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.3 (2013): 215-234. <http://eudml.org/doc/273024>.

@article{Blanchet2013,
abstract = {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.},
author = {Blanchet-Sadri, Francine, Simmons, Sean, Tebbe, Amelia, Veprauskas, Amy},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {combinatorics on words; Fine and Wilf’s theorem; partial words; abelian periods; periods; optimal lengths; Fine-Wilf theorem; abelian periodicity; partial word; optimal length},
language = {eng},
number = {3},
pages = {215-234},
publisher = {EDP-Sciences},
title = {Abelian periods, partial words, and an extension of a theorem of Fine and Wilf},
url = {http://eudml.org/doc/273024},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Blanchet-Sadri, Francine
AU - Simmons, Sean
AU - Tebbe, Amelia
AU - Veprauskas, Amy
TI - Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 3
SP - 215
EP - 234
AB - 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.
LA - eng
KW - combinatorics on words; Fine and Wilf’s theorem; partial words; abelian periods; periods; optimal lengths; Fine-Wilf theorem; abelian periodicity; partial word; optimal length
UR - http://eudml.org/doc/273024
ER -

References

top
  1. [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. Zbl1226.68074MR2594475
  2. [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). Zbl1247.68200
  3. [3] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci.218 (1999) 135–141. Zbl0916.68120MR1687780
  4. [4] F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton, FL (2008). Zbl1180.68205MR2384993
  5. [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. A119 (2012) 257–270. Zbl1233.68183MR2844095
  6. [6] F. Blanchet-Sadri, T. Mandel and G. Sisodia, Periods in partial words: An algorithm. J. Discrete Algorithms16 (2012) 113–128. Zbl1279.68279MR2960349
  7. [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. Zbl1213.68354MR2728320
  8. [8] F. Blanchet-Sadri, S. Simmons and D. Xu, Abelian repetitions in partial words. Adv. Appl. Math.48 (2012) 194–214. Zbl1231.68187MR2845515
  9. [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). Zbl1307.68059
  10. [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. Zbl0916.68114MR1687764
  11. [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. Zbl0866.68057MR1469998
  12. [12] S. Constantinescu and L. Ilie, Generalised Fine and Wilf’s theorem for arbitrary number of periods. Theor. Comput. Sci.339 (2005) 49–60. Zbl1127.68074MR2142073
  13. [13] S. Constantinescu and L. Ilie, Fine and Wilf’s theorem for abelian periods. Bull. Eur. Assoc. Theor. Comput. Sci.89 (2006) 167–170. Zbl1169.68561MR2267841
  14. [14] L.J. Cummings and W.F. Smyth, Weak repetitions in strings. J. Combin. Math. Combin. Comput.24 (1997) 33–48. Zbl0882.68111MR1451514
  15. [15] J. Currie and A. Aberkane, A cyclic binary morphism avoiding abelian fourth powers. Theoret. Comput. Sci.410 (2009) 44–52. Zbl1161.68044MR2488310
  16. [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. Zbl1221.68125MR2862727
  17. [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. Zbl1329.68197
  18. [18] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc.16 (1965) 109–114. Zbl0131.30203MR174934
  19. [19] V. Halava, T. Harju and T. Kärki, Interaction properties of relational periods. Discrete Math. Theoret. Comput. Sci.10 (2008) 87–112. Zbl1139.68045MR2393230
  20. [20] J. Justin, On a paper by Castelli, Mignosi, Restivo. Theoret. Inform. Appl. 34 (2000) 373–377. Zbl0987.68056MR1829233
  21. [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. MR1250629
  22. [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). Zbl1279.68240
  23. [23] A.M. Shur and Y.V. Gamzova, Partial words and the interaction property of periods. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya68 (2004) 191–214. Zbl1088.68147MR2058005
  24. [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. Zbl0999.68165MR1907051
  25. [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. Zbl1181.68181MR2553581
  26. [26] R. Tijdeman and L. Zamboni, Fine and Wilf words for any periods. Indagationes Math.14 (2003) 135–147. Zbl1091.68088MR2015604

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.