License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.45
URN: urn:nbn:de:0030-drops-69878
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6987/
Go to the corresponding LIPIcs Volume Portal

Kärkkäinen, Juha ; Kempa, Dominik ; Nakashima, Yuto ; Puglisi, Simon J. ; Shur, Arseny M.

On the Size of Lempel-Ziv and Lyndon Factorizations

pdf-format:
LIPIcs-STACS-2017-45.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{krkkinen_et_al:LIPIcs:2017:6987,
  author =	{Juha K{\"a}rkk{\"a}inen and Dominik Kempa and Yuto Nakashima and Simon J. Puglisi and Arseny M. Shur},
  title =	{{On the Size of Lempel-Ziv and Lyndon Factorizations}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{45:1--45:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6987},
  URN =		{urn:nbn:de:0030-drops-69878},
  doi =		{10.4230/LIPIcs.STACS.2017.45},
  annote =	{Keywords: Lempel-Ziv factorization, Lempel-Ziv parsing, LZ, Lyndon word, Lyndon factorization, Standard factorization}
}

Keywords: Lempel-Ziv factorization, Lempel-Ziv parsing, LZ, Lyndon word, Lyndon factorization, Standard factorization
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI