Periodicity on partial words
A partial word of length n over a finite alphabet A is a partial map from {0,..., n-1} into A. Elements of {0,..., n-1) without image are called holes (a word is just a partial word without holes). A fundamental periodicity result on words due to Fine and Wilf [1] intuitively determines how far two periodic events have to match in order to guarantee a common period. This result was extended to partial words with one hole by Berstel and Boasson [2] and to partial words with two or three holes by Blanchet-Sadri and Hegstrom [3]. In this paper, we give an extension to partial words with an arbitrary number of holes. (C) 2004 Elsevier Ltd. All rights reserved.
words combinatorial problems formal languages