2022/02/03 by Musthofa, Indah Emilia Wijayanti, Diah Junia Eksi Palupi +4
Computer Science · Mathematics · #Coding theory and cryptography #Cellular Automata and Applications #Advanced Combinatorial Mathematics
paper · pdf · doi:10.48550/arxiv.2202.01425
A binary modified de Bruijn sequence is an infinite and periodic binary sequence derived by removing a zero from the longest run of zeros in a binary de Bruijn sequence. The minimal polynomial of the modified sequence is its unique least-degree characteristic polynomial. Leveraging on a recent characterization, we devise a novel general approach to determine the minimal polynomial. We translate the characterization into a problem of identifying a Hamiltonian cycle in a specially constructed graph. Along the way, we demonstrate the usefullness of computational tools from the cycle joining method in the modified setup.