2020/10/15 by Evan Sala, Sala, Evan, Joe Sawada +3
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2010.07960
openalex publication_date 2020/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The greedy Prefer-same de Bruijn sequence construction was first presented by Eldert et al.[AIEE Transactions 77 (1958)]. As a greedy algorithm, it has one major downside: it requires an exponential amount of space to store the length 2n de Bruijn sequence. Though de Bruijn sequences have been heavily studied over the last 60 years, finding an efficient construction for the Prefer-same de Bruijn sequence has remained a tantalizing open problem. In this paper, we unveil the underlying structure of the Prefer-same de Bruijn sequence and solve the open problem by presenting an efficient algorithm to construct it using O(n) time per bit and only O(n) space. Following a similar approach, we also present an efficient algorithm to construct the Prefer-opposite de Bruijn sequence.