de Bruijn SequenceThe 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 lengthsDivisible 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. |