De Bruijn Partial Words

F. Blanchet-Sadri       Derek Allums       John Lensmire

Abstract       Implementation       Paper      

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.

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!