An efficient shift rule for the prefer-max de Bruijn sequence
From MaRDI portal
Publication:1618243
DOI10.1016/J.DISC.2018.09.024zbMATH Open1400.05004arXiv1706.01106OpenAlexW2622212042MaRDI QIDQ1618243FDOQ1618243
Authors: R. Smith 
Publication date: 13 November 2018
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: A shift rule for the prefer-max De Bruijn sequence is formulated, for all sequence orders, and over any finite alphabet. An efficient algorithm for this shift rule is presented, which has linear (in the sequence order) time and memory complexity.
Full work available at URL: https://arxiv.org/abs/1706.01106
Recommendations
- An efficient generalized shift-rule for the prefer-max de Bruijn sequence
- A simple shift rule for \(k\)-ary de Bruijn sequences
- Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions
- A framework for constructing de Bruijn sequences via simple successor rules
- An efficiently generated family of binary de Bruijn sequences
- De Bruijn sequences with efficient decoding algorithms
- An efficient implementation of the D-homomorphism for generation of de Bruijn sequences
- Designing preference functions for de Bruijn sequences with forbidden words
- On greedy algorithms for binary de Bruijn sequences
- Spans of preference functions for de Bruijn sequences
Cites Work
- Necklaces of beads in k colors and k-ary de Bruijn sequences
- A course in combinatorics.
- Factorizing words over an ordered alphabet
- Free differential calculus. IV: The quotient groups of the lower central series
- Generating necklaces
- Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
- Lexicographic compositions and de Bruijn sequences
- Generation of the Ford sequence of length \(2^ n\), n large
- A surprisingly simple de Bruijn sequence construction
- An algorithm for constructing m-ary de Bruijn sequences
- Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence
Cited In (5)
- Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions
- A simple shift rule for \(k\)-ary de Bruijn sequences
- An efficient generalized shift-rule for the prefer-max de Bruijn sequence
- On the \(k\)-error linear complexities of De Bruijn sequences
- Extending de Bruijn sequences to larger alphabets
This page was built for publication: An efficient shift rule for the prefer-max de Bruijn sequence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1618243)
