Periods, Partial Words, and a Result of Guibas and Odlyzko

F. Blanchet-Sadri and Brian Shirey

        A well known and unexpected result of Guibas and Odlyzko states that the set of all periods of a word is independent of the alphabet size (alphabets with one symbol are excluded here).  More specifically, for every word u, there exists a word v over the alphabet {0,1} such that u and v have the same length and the same set of periods. Recently, Blanchet-Sadri and Chriscoe extended this fundamental result to words with one "do not know" symbol also called partial words with one hole.  They showed that for every partial word u with one hole, there exists a partial word v with at most one hole over the alphabet {0,1} such that u and v have the same length, the same set of periods, the same set of weak periods, and H(v) Ì H(u), where H(u) (respectively, H(v)) denotes the set of holes of u (respectively, v).  In this paper, we extend this result further to a large class of partial words.  Given a partial word u belonging to that class, our proof provides an algorithm to compute a partial word v over {0,1} sharing the same length and same sets of periods and weak periods as u, and satisfying H(v) Ì H(u).

Keywords: Words, partial words, periods, and weak periods.

Valid XHTML 1.0!
Acknowledgement:This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-0207673 and 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.
Partial Words Logo
Valid CSS!