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:
“Much is made of the accelerating brutality of young people’s crimes, but rarely does our concern for dangerous children translate into concern for children in danger. We fail to make the connection between the use of force on children themselves, and violent antisocial behavior, or the connection between watching father batter mother and the child deducing a link between violence and masculinity.”
—Letty Cottin Pogrebin (20th century)