Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence

Patrick Baxter Dragon, Oscar I. Hernandez, Joe Sawada, Aaron Williams, Dennis Wong

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

A k-ary de Bruijn sequence of order n is a circular k-ary string of length kn which contains every k-ary string of length n exactly once as a substring. It is well-known that a k-ary de Bruijn sequence of order n can be constructed by concatenating the aperiodic prefixes of the k-ary necklaces of length n in lexicographic order. In this article we prove that an alternate de Bruijn sequence is created by replacing lexicographic order with co-lexicographic order. We also provide a simple successor rule for generating each successive symbol in O(n)-time.

Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalEuropean Journal of Combinatorics
Volume72
DOIs
Publication statusPublished - Aug 2018
Externally publishedYes

Fingerprint

Dive into the research topics of 'Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence'. Together they form a unique fingerprint.

Cite this