An Efficient Shift Rule for the Prefer-Max De Bruijn Sequence

2017/06/04 by Gal Amram, Yair Ashlagi, Amram, Gal +9
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Coding theory and cryptography #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1706.01106

openalex publication_date 2017/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• An Efficient Generalized Shift-Rule for the Prefer-Max De Bruijn Sequence
• A Cycle Joining Construction of the Prefer-Max De Bruijn Sequence
• Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
• To Infinity and Beyond: Continuing De Bruijn Sequences by Extending the Alphabet
• De Bruijn Sequences: From Games to Shift-Rules to a Proof of the Fredricksen-Kessler-Maiorana Theorem