Name
Abstract | ||
|---|---|---|
We show an application of Lempel's recursive construction of De Bruijn words to the generation of binary words having many factor-rich prefixes. A binary word is said to be factor-rich iff it has the largest number of distinct factors among binary words with the same length. A linear de Bruijn word of rank n is a shortest word containing (as a factor) exactly once each binary word of length n. It is factor-rich and its length equals Δn=2n+n−1. We construct for each n a binary linear de Bruijn word of rank n which is semi-perfect in the following sense: each of its prefixes of length m>Δn−1 is factor-rich. The number Δn−1 is the best possible (for n>2 there is no linear binary de Bruijn word with factor-rich prefix of length m=Δn−1). We show an efficient algorithm constructing compact description of binary semi-perfect de Bruijn words. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.tcs.2018.02.008 | Theoretical Computer Science |
Keywords | Field | DocType |
de Bruijn word,Semi-perfect,Straight-line program,Algorithm | Discrete mathematics,Combinatorics,Prefix,De Bruijn sequence,Mathematics,Recursion,Binary number | Journal |
Volume | ISSN | Citations |
720 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Damian Repke | 1 | 0 | 0.34 |
| wojciech rytter | 2 | 130 | 17.13 |