Constructing de Bruijn sequences by concatenating smaller universal cycles

2018/03/23 by Daniel Gabrić, Gabric, Daniel, Joe Sawada +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1803.09009

openalex publication_date 2018/03/23 · openalex created_date 2018/04/06 · openalex updated_date 2026/07/28

Abstract

We present sufficient conditions for when an ordering of universal cycles α₁, α₂, …, α_m for disjoint sets S₁, S₂, … , S_m can be concatenated together to obtain a universal cycle for S = S₁ ∪ S₂ ∪ ⋯ ∪ S_m. When S is the set of all k-ary strings of length n, the result of such a successful construction is a de Bruijn sequence. Our conditions are applied to generalize two previously known de Bruijn sequence constructions and then they are applied to develop three new de Bruijn sequence constructions.

Cited by

• Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random

Related

• Concatenation trees: A framework for efficient universal cycle and de Bruijn sequence constructions
• Contributions to the theory of de Bruijn cycles
• Cut-Down de Bruijn Sequences
• Generalized de Bruijn Cycles
• An Unoriented Variation on de Bruijn Sequences