A Successor Rule Framework for Constructing k-Ary de Bruijn Sequences and Universal Cycles

D. Gabric, J. Sawada, A. Williams, D. Wong

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

We present a simple framework for constructing k-ary 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 several previously known de Bruijn sequence constructions based on the pure cycling register and is applied to derive a new construction that is perhaps the simplest of all successors. Furthermore, it generalizes an algorithm to construct binary de Bruijn sequences based on any arbitrary nonsingular feedback function. The framework is applied to derive and prove the correctness of successors to efficiently construct 1) universal cycles for k-ary strings of length n whose weight is bounded by some w and 2) universal cycles for permutations. It has also been subsequently applied to find the first universal cycle constructions for weak orders.

Original languageEnglish
Article number8762187
Pages (from-to)679-687
Number of pages9
JournalIEEE Transactions on Information Theory
Volume66
Issue number1
DOIs
Publication statusPublished - Jan 2020
Externally publishedYes

Keywords

  • de Bruijn
  • feedback shift register
  • lyndon word
  • necklace
  • nonsingular feedback function
  • universal cycle

Fingerprint

Dive into the research topics of 'A Successor Rule Framework for Constructing k-Ary de Bruijn Sequences and Universal Cycles'. Together they form a unique fingerprint.

Cite this