Exploring the Greedy Constructions of de Bruijn Sequences

Thumbnail Image
Sala, Evan
Journal Title
Journal ISSN
Volume Title
University of Guelph

A k-ary de Bruijn sequence of order n is a cyclic sequence of length k^n such that each k-ary string of length n appears exactly once as a substring. These sequences have applications in a variety of fields, and can be constructed by a number of means, including graph based approaches, linear feedback shift registers, and greedy strategies. Some sequences generated by greedy approaches, such as the Ford sequence, can also be generated by other, more computationally efficient means. However, others, like the sequences produced by the prefer same and prefer opposite strategies, have no known efficient construction algorithm. The goal of this research is to find a more efficient method of generating the binary prefer same de Bruijn sequence. To this end, a previously unstudied feedback function is analyzed, and a new successor rule is described that efficiently constructs a binary de Bruijn sequence. Furthermore, we conjecture that a successor rule for the prefer same strategy can be constructed by applying the aforementioned feedback function.

de Bruijn Sequence, de Bruijn Graph, Greedy Algorithm, Sequence Construction