Unbordered Partial Words with a lot of Holes
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.
|
|
| 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. |
|
|
