hot pink!

F. Blanchet-Sadri       Kevin Corcoran       Jenell Nyberg

            

Abstract

The concept of periodicity has played over the years a central role in the development of combinatorics on words and has been a highly valuable tool for the design and analysis of algorithms. There are many fundamental periodicity results on words. Among them is the famous result of Fine and Wilf which intuitively determines how far two periodic events have to match in order to guarantee a common period. This result, which is one of the most widely used and known results on words, was extended to partial words, or sequences that may have a number of "do not know" symbols called "holes". More specifically, Fine and Wilf's result was extended to partial words with one hole by Berstel and Boasson, to partial words wtih two or three holes by Blanchet-Sadri and Hegstrom, and to partial words with an arbitrary number of holes by Blanchet-Sadri. In this paper, we study some consequences of these results.

Keywords:       Combinatorics on words; Fine and Wilf's periodicity result; Partial words; Periods; Weak periods.




Visit the NSF home page.

Acknowledgement:   This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020.

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.

Visit the Partial Words home page.

Valid XHTML 1.0! Valid CSS!