A de Bruijn sequence is a binary string of length 2^n that when considered cyclicly contains every binary string of length $n$ as a substring. For example 0000100110101111 is a de Bruijn sequence for n=4. It is well-known that each de Bruijn sequence is in 1-1 correspondence with an Euler cycle in a related de Bruijn graph. However, because the graph is exponential in size, there has been extensive research into the discovery of simple and efficient constructions for an arbitrary $n$. In this seminar we will discuss the state of the art with respect to de Bruijn sequence constructions at a level that will be accessible to a broad audience. Approaches will include: greedy algorithms, feedback shift registers, successor-rules, and (necklace) concatenation approaches. De Bruijn sequences have properties that are desirable for pseudo-random number generation, and the de Bruijn graph has found application in genome assembly. These sequences can also be generalized to a larger alphabet, and even considered in two dimensions on the torus.
Contact Person: Zsuzsanna Lipták
Strada le Grazie 15
VAT number 01541040232
Italian Fiscal Code 93009870234
© 2020 | Verona University | Credits