Name
Abstract | ||
|---|---|---|
Lyndon factorization and Lempel-Ziv (LZ) factorization are both important tools for analysing the structure and complexity of strings, but their combinatorial structure is very different. In this paper, we establish the first direct connection between the two by showing that while the Lyndon factorization can be bigger than the non-overlapping LZ factorization (which we demonstrate by describing a new, non-trivial family of strings) it is always less than twice the size. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.STACS.2017.45 | Leibniz International Proceedings in Informatics |
Keywords | DocType | Volume |
Lempel-Ziv factorization,Lempel-Ziv parsing,LZ,Lyndon word,Lyndon factorization,Standard factorization | Conference | 66 |
ISSN | Citations | PageRank |
1868-8969 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Juha Kärkkäinen | 1 | 1354 | 95.20 |
| Dominik Kempa | 2 | 142 | 16.37 |
| Yuto Nakashima | 3 | 57 | 19.52 |
| Simon J. Puglisi | 4 | 1132 | 75.14 |
| Arseny M. Shur | 5 | 152 | 26.47 |