Unbordered Partial Words with a lot of Holes

F. Blanchet-Sadri       Emily Allen       John Lensmire

Abstract       Implementation       Paper      

In this paper, we consider the problem of counting the number of unbordered partial words with h holes of length n over a k-size alphabet. This is related to the problem of computing the maximum number of holes an unbordered partial word with the parameters n, k can have. We obtain lower and upper bounds for that maximum number of holes, giving exact formulas in some cases.

Keywords:       Combinatorics on words; Partial Words; Unbordered Words.

Partial Words Logo
Valid XHTML 1.0!
Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. DMS-0754154. The Department of Defense is also gratefully acknowledged.
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.
Valid CSS!