Border Correlations of Binary Partial Words

Francine Blanchet-Sadri, Emily Clader, Olivia Simpson

Abstract

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)=c0c1 . . . cn-1 where ci =a or ci=b according to whether the ith cyclic shift σi(w) of w is unbordered or bordered. A partial word w is bordered if a proper prefix x1 of w is compatible with a proper suffix x2 of w, in which case any partial word x containing both x1 and x2 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 m0 m1 . . . mn-1 where m i is the length of a shortest border of σi(w). Our results extend those of Harju and Nowotka.

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




Valid XHTML 1.0! Valid CSS!