Understanding the prefer-same greedy construction of de Bruijn sequences
Speaker:
Evan Sala, University of Guelph
Date and Time:
Saturday, June 10, 2017 - 3:50pm to 4:15pm
Abstract:
A binary de Bruijn sequence is a circular sequence of length $2^n$ such that each length $n$ binary string appears exactly once as a substring. These sequences can be generated greedily, using simple rules and preference functions to determine the next element in a given sequence. Some sequences generated by greedy approaches, such as the Ford sequence, can also be generated by other, more computationally efficient means. The goal of this research is to find a more efficient method of generating the prefer same de Bruijn sequence.