Constructing de Bruijn sequences by concatenating smaller universal cycles

DOI10.1016/j.tcs.2018.06.039zbMath1398.68416arXiv1803.09009OpenAlexW2963943201MaRDI QIDQ1659978

Joe Sawada, Daniel Gabric

Publication date: 23 August 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.09009

zbMATH Keywords

de Bruijn sequenceLyndon wordnecklaceuniversal cycleco-necklaceconcatenation construction

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (3)

Constructing the first (and coolest) fixed-content universal cycle ⋮ Derivative-free mixed binary necklace optimization for cyclic-symmetry optimal design problems ⋮ Investigating the discrepancy property of de Bruijn sequences

Cites Work

• The lexicographically smallest universal cycle for binary strings with minimum specified weight
• Spans of preference functions for de Bruijn sequences
• A surprisingly simple de Bruijn sequence construction
• A simple shift rule for \(k\)-ary de Bruijn sequences
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence
• A de Bruijn sequence construction by concatenating cycles of the complemented cycling register
• Necklaces and Lyndon words in colexicographic and binary reflected Gray code order
• Self-dual sequences
• The Grandmama de Bruijn Sequence for Binary Strings
• Universal Cycles for Weight-Range Binary Strings
• De Bruijn Sequences for Fixed-Weight Binary Strings
• A Simple Combinatorial Algorithm for de Bruijn Sequences
• De Bruijn Sequences for the Binary Strings with Maximum Density
• An efficient algorithm for the generation of DeBruijn cycles
• A new algorithm for the generation of binary de Bruijn sequences
• Construction of de Bruijn sequences of minimal complexity
• An algorithm for constructing m-ary de Bruijn sequences
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• Generating necklaces
• A problem in arrangements
• The lexicographically least de Bruijn cycle

This page was built for publication: Constructing de Bruijn sequences by concatenating smaller universal cycles