Correlations of Partial Words
F. Blanchet-Sadri
blanchet@uncg.edu
      Joshua D. Gafni
jgafni@sas.upenn.edu
      Kevin H. Wilson
khwilson@umich.edu


Abstract


Partial words are strings over a finite alphabet that may contain a number of "do not know" symbols. In this paper, we introduce the notions of binary and ternary correlations, which are binary and ternary vectors indicating the periods and weak periods of partial words. Extending a result of Guibas and Odlyzko, we characterize precisely which of these vectors represent the (weak) period sets of partial words and prove that all valid correlations may be taken over the binary alphabet. We show that the sets of all such vectors of a given length form distributive lattices under inclusion. We also show that there is a well defined minimal set of generators for any binary correlation of length n and demonstrate that these generating sets are the primitive subsets of {1, 2,..., n-1}. Finally, we investigate the number of correlations of length n and the number of partial words sharing a given correlation.

Keywords: Combinatorics on words; Partial words; Correlations; Periods; Weak periods; Lattices; Primitive sets.