De Bruijn Sequences for the Binary Strings with Maximum Density

DOI10.1007/978-3-642-19094-0_19zbMath1317.68289MaRDI QIDQ3078396

Joe Sawada, Aaron Williams, Brett Stevens

Publication date: 20 February 2011

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_19

zbMATH Keywords

Lyndon words; de Bruijn sequence; necklaces; Gray codes; cool-lex order; fixed-density de Bruijn sequence

Mathematics Subject Classification ID

68R15: Combinatorics on words

68W32: Algorithms on strings

Related Items

The lexicographically smallest universal cycle for binary strings with minimum specified weight, The coolest way to generate binary strings, A surprisingly simple de Bruijn sequence construction, Binary bubble languages and cool-lex order, A universal cycle for strings with fixed-content (which are also known as multiset permutations), Constructing de Bruijn sequences by concatenating smaller universal cycles, A framework for constructing de Bruijn sequences via simple successor rules, Designing preference functions for de Bruijn sequences with forbidden words, Properties of the cycles that contain all vectors of weight \(\le k\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Gray code for fixed-density necklaces and Lyndon words in constant amortized time
• Binary bubble languages and cool-lex order
• The coolest way to generate combinations
• On universal cycles for multisets
• An algorithm for generating necklaces of beads in two colors
• Universal cycles for combinatorial structures
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Binary de Bruijn cycles under different equivalence relations
• De Bruijn Sequences for Fixed-Weight Binary Strings
• Generating necklaces