A framework for constructing de Bruijn sequences via simple successor rules

Daniel Gabric, Joe Sawada, Aaron Williams, Dennis Wong

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

Abstract

We present a simple framework for constructing de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes four previously known de Bruijn sequence constructions and is applied to derive three new and simple de Bruijn sequence constructions. Four of the constructions apply the pure cycling register and three apply the complemented cycling register. The correctness of each new construction is easily proved using the new framework. Each of the three new de Bruijn sequence constructions can be generated in O(n)-time per bit using O(n)-space.

Original languageEnglish
Pages (from-to)2977-2987
Number of pages11
JournalDiscrete Mathematics
Volume341
Issue number11
DOIs
Publication statusPublished - Nov 2018
Externally publishedYes

Fingerprint

Dive into the research topics of 'A framework for constructing de Bruijn sequences via simple successor rules'. Together they form a unique fingerprint.

Cite this