De Bruijn Sequence and Universal Cycle Constructions

Given an alphabet of size $k$, a de Bruijn (DB) sequence of order $n$ is a circular string of length $k^n$ where every $k$-ary string of length $n$ appears exactly once as a substring.

This inspiration for this project is to update Fredricksen's survey [SIAM Review, Vol 24 (1982)] to include new results and constructions from the past 40 years. The following different construction methods are presented:

• Euler cycles based on the de Bruijn graph
• Linear feedback shift registers (LFSRs)
• Recursive methods
• Greedy methods
• Shift (successor) rules based on cycle joining
• Concatenation approaches

Additionally, there is an algorithm to decode the lexicographically smallest DB sequence (the Granddaddy) and a section on properties including an analysis of DB sequence discrepancies.

More generally, a universal cycle of order $n$ for a set $\mathbf{S}$ of length $n$ strings is a circular string of length $|\mathbf{S}|$ where every string in $\mathbf{S}$ appears exactly once as a substring. Universal cycle constructions are provided for:

• Permutations (shorthand)
• Multiset permutations (strings with fixed content)
• Weak orders - both height and rank representations
• Cut-down DB sequences
• Orientable sequences