Necklaces of beads in k colors and k-ary de Bruijn sequences

DOI10.1016/0012-365X(78)90002-XzbMath0384.05004OpenAlexW1976395511WikidataQ55951860 ScholiaQ55951860MaRDI QIDQ1248514

Publication date: 1978

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

Full work available at URL: https://doi.org/10.1016/0012-365x(78)90002-x

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Enumerative combinatorics (05A99) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Related Items (67)

An efficient shift rule for the prefer-max de Bruijn sequence ⋮ Indeterminate string factorizations and degenerate text transformations ⋮ An algorithm for generating necklaces of beads in two colors ⋮ On the theorem of Fredricksen and Maiorana about de Bruijn sequences ⋮ A universal cycle for strings with fixed-content (which are also known as multiset permutations) ⋮ Lyndon words formalized in Isabelle/HOL ⋮ Lyndon + Christoffel = digitally convex ⋮ Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles ⋮ Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence ⋮ Two new optimal ternary two-weight codes and strongly regular graphs ⋮ Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences ⋮ Constructing de Bruijn sequences by concatenating smaller universal cycles ⋮ Linearization of multi-valued nonlinear feedback shift registers ⋮ The origins of combinatorics on words ⋮ Fractional covers for convolution products ⋮ Generalized Fibonacci recurrences and the lex-least de Bruijn sequence ⋮ Unnamed Item ⋮ Necklaces and Lyndon words in colexicographic and binary reflected Gray code order ⋮ Computing generalized de Bruijn sequences ⋮ A Gray code for fixed-density necklaces and Lyndon words in constant amortized time ⋮ Boltzmann samplers for \(v\)-balanced cycles ⋮ Lyndon words and Fibonacci numbers ⋮ Linear computation of unbordered conjugate on unordered alphabet ⋮ Words with many palindrome pair factors ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ The lexicographically smallest universal cycle for binary strings with minimum specified weight ⋮ Finding the cyclic covers of a string ⋮ Constructing the first (and coolest) fixed-content universal cycle ⋮ String rearrangement inequalities and a total order between primitive words ⋮ Analysis of generating functions for special words and numbers and algorithms for computation ⋮ Generation of some de Bruijn sequences ⋮ Ranking and Unranking k-Subsequence Universal Words ⋮ Completely uniformly distributed sequences based on de Bruijn sequences ⋮ Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions ⋮ Corrigendum to ``On the theorem of Fredricksen and Maiorana about de Bruijn sequences ⋮ The coolest way to generate binary strings ⋮ A surprisingly simple de Bruijn sequence construction ⋮ 2D Lyndon words and applications ⋮ A new look at the de Bruijn graph ⋮ On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties ⋮ The standard factorization of Lyndon words: an average point of view ⋮ Necklaces and bracelets in R ⋮ Burrows-Wheeler transformations and de Bruijn words ⋮ Test sequence construction using minimum information on the tested system ⋮ Witt vectors. Part 1 ⋮ A framework for constructing de Bruijn sequences via simple successor rules ⋮ An efficient generalized shift-rule for the prefer-max de Bruijn sequence ⋮ Decoding structured light patterns for three-dimensional imaging systems ⋮ A simple shift rule for \(k\)-ary de Bruijn sequences ⋮ Inverse Lyndon words and inverse Lyndon factorizations of words ⋮ Generalized de Bruijn words for primitive words and powers ⋮ Combinatorial View of Digital Convexity ⋮ The Collatz conjecture and de Bruijn graphs ⋮ De Bruijn Sequences for the Binary Strings with Maximum Density ⋮ Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence ⋮ Two linear-time algorithms for computing the minimum length polygon of a digital contour ⋮ Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour ⋮ Circular slider graphs: de Bruijn, Kautz, Rauzy, lamplighters and spiders ⋮ Investigating the discrepancy property of de Bruijn sequences ⋮ On stability of multi-valued nonlinear feedback shift registers ⋮ On greedy algorithms for binary de Bruijn sequences ⋮ de Bruijn sequences and de Bruijn graphs for a general language ⋮ Minimum Eulerian circuits and minimum de Bruijn sequences ⋮ Gray cycles of maximum length related to \(k\)-character substitutions ⋮ Charm bracelets and their application to the construction of periodic Golay pairs ⋮ Longest Lyndon Substring After Edit ⋮ Computation of k-ary Lyndon words using generating functions and their differential equations

Cites Work

This page was built for publication: Necklaces of beads in k colors and k-ary de Bruijn sequences