An efficient shift rule for the prefer-max de Bruijn sequence

DOI10.1016/J.DISC.2018.09.024MaRDI QIDQ1618243zbMATH OpenOpenAlexFDO

Authors R. Smith

Publication date 13 November 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

de Bruijn sequenceFord sequenceprefer-max sequenceshift rule

Mathematics Subject Classification ID

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

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.

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

• A course in combinatorics.
• 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
• Factorizing words over an ordered alphabet
• Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
• Free differential calculus. IV: The quotient groups of the lower central series
• Generating necklaces
• Generation of the Ford sequence of length \(2^ n\), n large
• Lexicographic compositions and de Bruijn sequences
• Necklaces of beads in k colors and k-ary de Bruijn sequences

Cited in

(6)

• On the \(k\)-error linear complexities of De Bruijn sequences
• Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions
• An efficient generalized shift-rule for the prefer-max de Bruijn sequence
• Extending de Bruijn sequences to larger alphabets
• De Bruijn sequences: from games to shift-rules to a proof of the Fredricksen-Kessler-Maiorana theorem
• A simple shift rule for \(k\)-ary de Bruijn sequences

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)