Name
Abstract | ||
|---|---|---|
A de Bruijn sequence is a circular binary string of length 2n that contains each binary string of length n exactly once as a substring. A maximum-density de Bruijn sequence is a circular binary string of length n (n 0)+(n 1)+(n 2)+...+(n m) that contains each binary string of length n with density (number of 1s) between 0 and m, inclusively. In this paper we efficiently generate maximum-density de Bruijn sequences for all values of n and m. An interesting special case occurs when n = 2m+1. In this case our result is a "complement-free de Bruijn sequence" since it is a circular binary string of length 2n-1 that contains each binary string of length n or its complement exactly once as a substring. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-19094-0_19 | WALCOM |
Keywords | Field | DocType |
n m,de bruijn sequence,maximum density,length n,interesting special case,binary string,circular binary string | Discrete mathematics,Combinatorics,Substring,Binary strings,Gray code,De Bruijn graph,De Bruijn sequence,Lyndon words,Mathematics,Maximum density | Conference |
Volume | ISSN | Citations |
6552 | 0302-9743 | 6 |
PageRank | References | Authors |
0.52 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joe Sawada | 1 | 66 | 9.11 |
| Brett Stevens | 2 | 222 | 31.38 |
| Aaron Williams | 3 | 139 | 20.42 |