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) = 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.

Border Correlations of Partial Words
PDF (Portable Document Format)
444 KB
Created on 2/18/2011
Views: 2020

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