2026-07-28T15:23:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6987 2024-03-06T10:39:13Z ddc:004 open_access

On the Size of Lempel-Ziv and Lyndon Factorizations Kärkkäinen, Juha Kempa, Dominik Nakashima, Yuto Puglisi, Simon J. Shur, Arseny M. Lempel-Ziv factorization Lempel-Ziv parsing LZ Lyndon word Lyndon factorization Standard factorization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Juha Kärkkäinen and Dominik Kempa and Yuto Nakashima and Simon J. Puglisi and Arseny M. Shur 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.45 urn:nbn:de:0030-drops-69878 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.45 eng https://creativecommons.org/licenses/by/3.0/legalcode