Border Correlations of Partial Words

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

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 → {◊}, 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 partial 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* * that maps a partial word w of length n to m0m1...mn-1 where mi is the length of a shortest border of σi(w). Our results extend those of Harju and Nowotka.

Additional Information

Publication
Theory of Computing Systems, Vol. 47, No. 1, pp 179-195.
Language: English
Date: 2010
Keywords
Combinatorics on words, Partial words, Border correlations

Email this document to