Border Correlations of Binary Partial Words

Partial words are finite sequences over a finite alphabet A that may contain a number of "do not know" symbols, denoted by ◊'s. Setting A_◊=A ∪ {◊}, A_◊^* denotes the set of all partial words over A. In this paper, we investigate the border correlation function β: A_◊^* → {a, b}^* that specifies which conjugates (cyclic shifts) of a given word w of length n are bordered, that is, β(w)=c₀c₁ . . . c_n-1 where c_i =a or c_i=b according to whether the ith cyclic shift σⁱ(w) of w is unbordered or bordered. A partial word w is bordered if a proper prefix x₁ of w is compatible with a proper suffix x₂ of w, in which case any partial word x containing both x₁ and x₂ is called a border of w. In addition to β, we investigate an extension β':{a, b}_◊^* → N^* that maps a partial word w of length n to m₀ m₁ . . . m_n-1 where m _i is the length of a shortest border of σⁱ(w). Our results extend those of Harju and Nowotka.

Keywords: Combinatorics on words; Border correlations; Partial words.