Rule-based Generation of de Bruijn Sequences: Memory and Learning

2025/07/13 by Muñoz, Francisco J., Nuño, Juan Carlos
#Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2507.09764

Abstract

We investigate binary sequences generated by non-Markovian rules with memory length μ, similar to those adopted in Elementary Cellular Automata. This generation procedure is equivalente to a shift register and certain rules produce sequences with maximal periods, known as de Bruijn sequences. We introduce a novel methodology for generating de Bruijn sequences that combines: (i) a set of derived properties that significantly reduce the space of feasible generating rules, and (ii) a neural network-based classifier that identifies which rules produce de Bruijn sequences. Experiments for large values of μ demonstrate the approach's effectiveness and computational efficiency.

Related

• New Successor Rules to Efficiently Produce Exponentially Many Binary de Bruijn Sequences
• Cut-Down de Bruijn Sequences
• An Efficient Generalized 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
• Spans of Preference Functions for De Bruijn Sequences