@inproceedings{858e75397c42440296f82554fef4be5c,
title = "On the size of Lempel-Ziv and Lyndon factorizations",
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.",
keywords = "Lempel-Ziv factorization, Lempel-Ziv parsing, Lyndon factorization, Lyndon word, LZ, Standard factorization",
author = "Juha K{\"a}rkk{\"a}inen and Dominik Kempa and Yuto Nakashima and Puglisi, \{Simon J.\} and Shur, \{Arseny M.\}",
note = "Publisher Copyright: {\textcopyright} Juha K{\"a}rkk{\"a}inen, Dominik Kempa, Yuto Nakashima, Simon J. Puglisi, and Arseny M. Shur.; 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017 ; Conference date: 08-03-2017 Through 11-03-2017",
year = "2017",
month = mar,
day = "1",
doi = "10.4230/LIPIcs.STACS.2017.45",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Brigitte Vallee and Heribert Vollmer",
booktitle = "34th Symposium on Theoretical Aspects of Computer Science, STACS 2017",
}