A New Approach to Determine the Minimal Polynomials of Binary Modified de Bruijn Sequences

Musthofa, Indah Emilia Wijayanti, Diah Junia Eksi Palupi and Martianus Frederic Ezerman
Additional contact information
Musthofa: Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Gadjah Mada, Sekip Utara BLS 21, Yogyakarta 55281, Indonesia
Indah Emilia Wijayanti: Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Gadjah Mada, Sekip Utara BLS 21, Yogyakarta 55281, Indonesia
Diah Junia Eksi Palupi: Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Gadjah Mada, Sekip Utara BLS 21, Yogyakarta 55281, Indonesia
Martianus Frederic Ezerman: School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, Singapore 637371, Singapore

Mathematics, 2022, vol. 10, issue 15, 1-18

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.

Keywords: binary sequence; Hamiltonian cycle; linear span; minimal polynomial; modified de Bruijn sequence (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/15/2577/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/15/2577/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:15:p:2577-:d:871003

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().