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

研究成果: Article同行評審

15 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)1-11
頁數11
期刊European Journal of Combinatorics
72
DOIs
出版狀態Published - 8月 2018
對外發佈

指紋

深入研究「Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence」主題。共同形成了獨特的指紋。

引用此