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

2018/01/30 by Amram, Gal, Rubin, Amir
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1801.10091

Abstract

One of the fundamental ways to construct De Bruijn sequences is by using a shift-rule. A shift-rule receives a word as an argument and computes the symbol that appears after it in the sequence. An optimal shift-rule for an (n,k)-De Bruijn sequence runs in time O(n). We propose an extended notion we name a generalized-shift-rule, which receives a word, w, and an integer, c, and outputs the c symbols that comes after w. An optimal generalized-shift-rule for an (n,k)-De Bruijn sequence runs in time O(n+c). We show that, unlike in the case of a shift-rule, a time optimal generalized-shift-rule allows to construct the entire sequence efficiently. We provide a time optimal generalized-shift-rule for the well-known prefer-max and prefer-min De Bruijn sequences.

Related

• An Efficient Shift Rule for the Prefer-Max De Bruijn Sequence
• De Bruijn Sequences: From Games to Shift-Rules to a Proof of the Fredricksen-Kessler-Maiorana Theorem
• A Cycle Joining Construction of the Prefer-Max De Bruijn Sequence
• Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
• New Successor Rules to Efficiently Produce Exponentially Many Binary de Bruijn Sequences