De Bruijn Partial Words

F. Blanchet-Sadri       Derek Allums       John Lensmire

Abstract       Implementation       Paper      

For a given order n and generating word z, the applet below will calculate (if possible) the shortest word w with subword complexity 2n that contains z. The word w is generated using a connected graph that has an Eulerian path. The applet outputs information about this graph, as well as the resulting word w, its complexity, and its length. The applet accepts only binary generating words (that is over an alphabet {a,b}) with 0, 1, or 2 holes (where a hole is denoted by '^'). Furthermore, the generating word must contain a nonoverlapping prefix and suffix of length at least n-1 that are each full.

This page may not function correctly if you do not have the latest Java Runtime Environment and the latest Java Plugin.

 

Get Java Now!


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!