Necklaces and Lyndon words in colexicographic and binary reflected Gray code order

DOI10.1016/j.jda.2017.10.002zbMath1374.68731OpenAlexW2762796277MaRDI QIDQ1679610

Aaron Williams, Dennis Wong, Joe Sawada

Publication date: 9 November 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2017.10.002

zbMATH Keywords

Gray codede Bruijn sequenceLyndon wordpseudo-necklacenecklace

Mathematics Subject Classification ID

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

Related Items

Inside the binary reflected gray code: flip-swap languages in 2-gray code order, Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence, Constructing de Bruijn sequences by concatenating smaller universal cycles, Flip-swap languages in binary reflected Gray code order

Cites Work

• Unnamed Item
• Unnamed Item
• A Gray code for fixed-density necklaces and Lyndon words in constant amortized time
• Gray-ordered binary necklaces
• More restrictive Gray codes for necklaces and Lyndon words
• An algorithm for generating necklaces of beads in two colors
• Lexicographically least circular substrings
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• The Grandmama de Bruijn Sequence for Binary Strings
• Generating necklaces
• Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
• A Gray Code for Necklaces of Fixed Density
• An Efficient Algorithm for Generating Necklaces with Fixed Density