To Infinity and Beyond: Continuing De Bruijn Sequences by Extending the Alphabet

2019/06/10 by Svoray, Yotam, Weiss, Gera
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1906.06157

Abstract

This article presents proof that the reverse of the Prefer Max De Bruijn sequence can be expanded into an infinite De Bruijn sequence by increasing the size of the alphabet. Furthermore, we show that every De Bruijn sequence possessing this characteristic exhibits behavior similar to that of the reverse of the Prefer Max De Bruijn sequence.

Related

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