De Bruijn sequence constructions

Joseph Sawada - University of Guelph, Canada
Date and time
Tuesday, June 18, 2019 at 4:30 PM - Sala Verde
Programme Director
External reference
Publication date
May 20, 2019
Computer Science  


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

© 2002 - 2021  Verona University
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234