Main content

Exploring the Greedy Constructions of de Bruijn Sequences

Show full item record

Title: Exploring the Greedy Constructions of de Bruijn Sequences
Author: Sala, Evan
Department: School of Computer Science
Program: Computer Science
Advisor: Sawada, Joseph
Abstract: 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.
Date: 2018-05
Rights: Attribution-NonCommercial-ShareAlike 2.5 Canada
Terms of Use: All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.

Files in this item

Files Size Format View
Sala_Evan_201805_MSc.pdf 853.6Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Attribution-NonCommercial-ShareAlike 2.5 Canada Except where otherwise noted, this item's license is described as Attribution-NonCommercial-ShareAlike 2.5 Canada