Connection To De Bruijn Sequences
If one concatenates together, in lexicographic order, all the Lyndon words that have length dividing a given number n, the result is a de Bruijn sequence, a circular sequence of symbols such that each possible length-n sequence appears exactly once as one of its contiguous subsequences. For example, the concatenation of the binary Lyndon words whose length divides four is
- 0 0001 0011 01 0111 1
This construction, together with the efficient generation of Lyndon words, provides an efficient method for constructing a particular de Bruijn sequence in linear time and logarithmic space.
Read more about this topic: Lyndon Word
Famous quotes containing the word connection:
“Morality becomes hypocrisy if it means accepting mothers’ suffering or dying in connection with unwanted pregnancies and illegal abortions and unwanted children.”
—Gro Harlem Brundtland (b. 1939)