Abelian Repetitions in Partial Words

F. Blanchet-Sadri       Sean Simmons       Dimin Xu

Abstract       Implementation       Paper      

We study abelian repetitions in partial words. We investigate the avoidance of abelian pth powers in infinite partial words, for p greater than two (the case of p equal to two was studied in some recent papers). In particular, we ask, for a given p, what is the smallest alphabet size so that there exists an infinite word with finitely or infinitely many holes that avoids abelian pth powers. We also investigate the problem of arbitrary insertion of holes into an infinite full word. We prove that if we insert arbitrarily many holes into an infinite abelian p-free full word, the resulting partial word is no longer abelian p-free.

Keywords:       Combinatorics on Words; Partial Words; Abelian Repetitions.


Partial Words Logo
Valid XHTML 1.0!
Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. DMS-0754154. The Department of Defense is also gratefully acknowledged.
Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
NSF
Valid CSS!