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.
NSF
Valid CSS!