Border Correlations of 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_{\diamond}=A\cup\lbrace{\diamond}\rbracePartial 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_{\diamond}=A\cup\lbrace{\diamond}\rbrace , A _⋄ ^* denotes the set of all partial words over A. In this paper, we investigate the border correlation function b:A_à^*?{a,b}^*\beta:A_{\diamond}^{*}\rightarrow\lbrace a,b\rbrace^{*} that specifies which conjugates (cyclic shifts) of a given partial 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 _⋄ ^*→ℕ^* 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.