unbordered partial words

F. Blanchet-Sadri, C.D. Davis,
Joel Dodge, Robert Mercas,
and Margaret Moorefield

An unbordered word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend results on unbordered words to unbordered partial words. Partial words are strings that may have a number of “do not know” symbols. We extend a result of Ehrenfeucht and Silberger which states that if a word u can be written as a concatenation of nonempty prefixes of a word v, then u can be written as a unique concatenation of nonempty unbordered prefixes of v. We study properties of the longest unbordered prefix of a partial word, investigate the relationship between the minimal weak period of a partial word and the maximal length of its unbordered factors, and also investigate some of the properties of an unbordered partial word and how they relate to its critical factorizations (if any).

Keywords:  Words, partial words, unbordered words, unbordered partial words.

Visit the NSF home page.

Acknowledgement:   This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-0207673 and DMS-0452020.

Disclaimer:   Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Visit the Partial Words research home page.

Valid XHTML 1.0! Valid CSS!

Implementations and web pages by Charles Bevan, Alexey Bogaevski and Margaret Moorefield.