|
|
|
The shortest sequence such that every string of length 
on the Alphabet 
occurs as a contiguous subrange of the
sequence described by . Every de Bruijn sequence corresponds to an Eulerian Cycle on a de Bruijn Graph.
Surprisingly, it turns out that the lexicographic sequence of Lyndon Words of lengths
Divisible by gives the lexicographically smallest de Bruijn sequence (Ruskey).
References
Ruskey, F. ``Information on Necklaces, Lyndon Words, de Bruijn Sequences.''
http://sue.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html.