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