A surprisingly simple de Bruijn sequence construction

DOI10.1016/J.DISC.2015.08.002MaRDI QIDQ501039zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A de Bruijn sequence construction by concatenating cycles of the complemented cycling register
• A simple shift rule for \(k\)-ary de Bruijn sequences
• A simple combinatorial algorithm for 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

Cites work

• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A class of nonlinear de Bruijn cycles
• A new algorithm for the generation of binary de Bruijn sequences
• A new memoryless algorithm for de Bruijn sequences
• A problem in arrangements
• A simple combinatorial algorithm for de Bruijn sequences
• Algorithms for the generation of full-length shift- register sequences
• De Bruijn sequences for the binary strings with maximum density
• Generation of the Ford sequence of length \(2^ n\), n large
• Lexicographic compositions and de Bruijn sequences
• Lexicographically least circular substrings
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Universal Cycles for Weight-Range Binary Strings

Cited in

(20)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501039)