A simple shift rule for \(k\)-ary de Bruijn sequences

DOI10.1016/j.disc.2016.09.008zbMath1351.05022OpenAlexW2551168410MaRDI QIDQ729788

Aaron Williams, Dennis Wong, Joe Sawada

Publication date: 22 December 2016

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

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

zbMATH Keywords

de Bruijn sequencenecklacesuniversal cycleCAT algorithmgenerateshift rulesuccessor rule\(k\)-ary de Bruijn sequenceshift Gray code

Mathematics Subject Classification ID

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

Related Items (6)

Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence ⋮ Constructing de Bruijn sequences by concatenating smaller universal cycles ⋮ An efficiently generated family of binary de Bruijn sequences ⋮ An efficient generalized shift-rule for the prefer-max de Bruijn sequence ⋮ Circular slider graphs: de Bruijn, Kautz, Rauzy, lamplighters and spiders ⋮ On greedy algorithms for binary de Bruijn sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Spans of preference functions for de Bruijn sequences
• A surprisingly simple de Bruijn sequence construction
• 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
• Factorizing words over an ordered alphabet
• 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 Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• A problem in arrangements
• Note on a Paper By I. J. Good

This page was built for publication: A simple shift rule for \(k\)-ary de Bruijn sequences