Combinatorics on Partial Word Correlations

F. Blanchet-Sadri, Justin Fowler, Gary Gramajo

Abstract                 Implementation                 Paper

Recently, Blanchet-Sadri, Gafni and Wilson considered the period and weak period sets of partial words of length n over a finite alphabet, and introduced specific representations of them, correlations, which are binary and ternary vectors of length n indicating the periods and weak periods. In this paper, we pursue their study of the combinatorics on partial word correlations. In particular, we investigate the population size, that is, the number of partial words sharing a given correlation, and obtain recurrences to compute it. Our results generalize those of Guibas, Odlyzko, Rivals and Rahmann.

Keywords:  Combinatorics on words; Partial words; Correlations, Periods, Weak periods, Population size.

Valid XHTML 1.0! Valid CSS!