Border Correlations on Partial Words
Francine Blanchet-Sadri     Michelle Cordier     Rachel Kirsch


Partial words are sequences over a finite alphabet that may contain some "do not know" symbols. In this paper, we consider the border sets of partial words of length n, and study the combinatorics of specific representations of them, called border correlations, which are binary vectors of length n indicating the borders. We characterize precisely which of these vectors are valid border correlations, and establish a one-to-one correspondence between the set of valid border correlations and the set of valid ternary correlations of a given length, the latter being ternary vectors representing the strong and strictly weak period sets. We investigate the population size, that is, the number of partial words sharing a given border correlation, and obtain formulas to compute it. We also give a correspondence between the ternary correlation of a partial word and its refined border correlation, which specifies the lengths of all the word's bordered cyclic shifts' shortest borders.

Keywords: Combinatorics on words; Partial words; Border correlations; Refined border correlations; Ternary correlations; Population size.


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

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
XHTML 1.0!