ABSTRACT
In this chapter, we study the combinatorics of possible sets of periods and weak periods of partial words. In Section 11.1, we introduce the notions of binary and ternary correlations, which are binary and ternary vectors indicating the periods and weak periods of partial words. In Section 11.2, we characterize precisely which of these vectors represent the period and weak period sets of partial words and prove that all valid correlations may be taken over the binary alphabet. In Section 11.3, we show that the sets of all such vectors of a given length form distributive lattices under suitably defined partial orderings. In Section 11.4, we show that there is a well defined minimal set of generators, which we call an irreducible set of periods, for any binary correlation of length n and demonstrate in Section 11.5 that these generating sets are the so-called primitive subsets of {1, 2, ..., n − 1}. Finally, we investigate the number of partial word correlations of length n.
