A new approach to determine the minimal polynomials of binary modified de Bruijn sequences

Abstract

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 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. The graph is isomorphic to the modified de Bruijn--Good graph. Along the way, we demonstrate the usefulness of some computational tools from the cycle joining method in the modified setup.