De Bruijn Sequences: from Games to Shift-Rules to a Proof of the Fredricksen-Kessler-Maiorana Theorem

Abstract

We present a combinatorial game and propose efficiently computable optimal strategies. We then show how these strategies can be translated to efficiently computable shift-rules for the well known prefer-max and prefer-min De Bruijn sequences, in both forward and backward directions. Using these shift-rules, we provide a new proof of the well known theorem by Fredricksen, Kessler, and Maiorana on De Bruijn sequences and Lyndon words.