A surprisingly simple de Bruijn sequence construction

DOI10.1016/j.disc.2015.08.002zbMath1322.05013OpenAlexW1745342855MaRDI QIDQ501039

Joe Sawada, Aaron Williams, Dennis Wong

Publication date: 8 October 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2015.08.002

zbMATH Keywords

de Bruijn sequencenecklacesuniversal cycleCAT algorithmgenerateshift gray codeshift rulesuccessor rule

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Special sequences and polynomials (11B83)

Related Items (14)

An efficient shift rule for the prefer-max de Bruijn sequence ⋮ Constructing de Bruijn sequences by concatenating smaller universal cycles ⋮ A new upper bound on the order of affine sub-families of NFSRs ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Two-way machines and de Bruijn words ⋮ An interleaved method for constructing de Bruijn sequences ⋮ An efficiently generated family of binary de Bruijn sequences ⋮ A framework for constructing de Bruijn sequences via simple successor rules ⋮ An efficient generalized shift-rule for the prefer-max de Bruijn sequence ⋮ A simple shift rule for \(k\)-ary de Bruijn sequences ⋮ On the \(k\)-error linear complexities of De Bruijn sequences ⋮ Investigating the discrepancy property of de Bruijn sequences ⋮ On greedy algorithms for binary de Bruijn sequences

Cites Work

• Unnamed Item
• Lexicographically least circular substrings
• A class of nonlinear de Bruijn cycles
• Lexicographic compositions and de Bruijn sequences
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Generation of the Ford sequence of length \(2^ n\), n large
• Universal Cycles for Weight-Range Binary Strings
• A Simple Combinatorial Algorithm for de Bruijn Sequences
• De Bruijn Sequences for the Binary Strings with Maximum Density
• Algorithms for the generation of full-length shift- register sequences
• A new algorithm for the generation of binary de Bruijn sequences
• A new memoryless algorithm for de Bruijn sequences
• A problem in arrangements

This page was built for publication: A surprisingly simple de Bruijn sequence construction