Name
Abstract | ||
|---|---|---|
Covers, being one of the most popular form of regularities in strings, have drawn much attention in the relevant literature. In this paper, we focus on the problem of linear-time inference of strings from cover arrays using the least sized alphabet. We present an algorithm that can reconstruct a string x over a binary alphabet whenever a valid cover array C is given as an input. We have devised our algorithm using several interesting combinatorial properties of cover arrays as well as an interesting relation between border array and cover array. Our algorithm runs in linear-time. The fact that, from any valid cover array, we can infer a binary string x, is, in itself, a fascinating result in stringology, and this work may be considered as the final step for this particular problem area. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1142/S1793830913600057 | DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS |
Keywords | Field | DocType |
Cover array, string inference | Discrete mathematics,Combinatorics,Inference,Binary strings,Mathematics,Binary number,Alphabet | Journal |
Volume | Issue | ISSN |
5 | 2 | 1793-8309 |
Citations | PageRank | References |
1 | 0.36 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tanaeem M. Moosa | 1 | 68 | 5.26 |
| Sumaiya Nazeen | 2 | 8 | 1.57 |
| M. Sohel Rahman | 3 | 488 | 56.99 |
| Rezwana Reaz | 4 | 11 | 3.32 |