Name
Abstract | ||
|---|---|---|
A de Bruijn sequence is a binary string of length (2^n) which, when viewed cyclically, contains every binary string of length n exactly once as a substring. Knuth refers to the lexicographically least de Bruijn sequence for each n as the “granddaddy” and Fredricksen et al. showed that it can be constructed by concatenating the aperiodic prefixes of the binary necklaces of length n in lexicographic order. In this paper we prove that the granddaddy has a lexicographic partner. The “grandmama” sequence is constructed by instead concatenating the aperiodic prefixes in co-lexicographic order. We explain how our sequence differs from the previous sequence and why it had not previously been discovered. |
Year | Venue | Field |
|---|---|---|
2016 | LATIN | Discrete mathematics,Substring,Combinatorics,Computer science,De Bruijn graph,Concatenation,Lexicographical order,De Bruijn sequence,Lyndon word,Aperiodic graph,Binary number |
DocType | Citations | PageRank |
Conference | 3 | 0.42 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patrick Baxter Dragon | 1 | 3 | 0.42 |
| Oscar I. Hernandez | 2 | 3 | 0.42 |
| Aaron Williams | 3 | 139 | 20.42 |