A De Bruijn partial word of order n over a k-ary alphabet is a minimal length partial word such that every word of length n is compatible with factors of it. To construct such words, one can delete and add certain edges from a De Bruijn graph in such a way that a minimal length Eulerian path exists. We discuss in detail this technique, and also analyze the special cases of binary De Bruijn words with two holes as well as k-ary De Bruijn words with one hole; each of some order n.
Keywords: Combinatorics on Words; Graph Theory; Partial Words; De Bruijn 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. |
|
|
