Title | ||
---|---|---|
Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence. |
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. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.ejc.2018.03.006 | European Journal of Combinatorics |
Field | DocType | Volume |
Discrete mathematics,Substring,Combinatorics,Prefix,Concatenation,De Bruijn sequence,Lexicographical order,Aperiodic graph,Mathematics | Journal | 72 |
ISSN | Citations | PageRank |
0195-6698 | 3 | 0.40 |
References | Authors | |
11 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Patrick Baxter Dragon | 1 | 3 | 0.40 |
Oscar I. Hernandez | 2 | 3 | 0.40 |
Joe Sawada | 3 | 66 | 9.11 |
Aaron Williams | 4 | 139 | 20.42 |
Dennis Wong | 5 | 22 | 3.80 |