On the size of overlapping Lempel-Ziv and Lyndon factorizations

DOI10.4230/LIPIcs.CPM.2019.29OpenAlexW2954309532MaRDI QIDQ5088921

Yuto Nakashima, Yuki Urabe, Shunsuke Inenaga, Masayuki Takeda, Hideo Bannai

Publication date: 18 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.CPM.2019.29

zbMATH Keywords

Lyndon wordsLyndon factorizationLempel-Ziv factorization

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (2)

On the approximation ratio of LZ-end to LZ77 ⋮ Can formal languages help pangenomics to represent and analyze multiple genomes?

Cites Work

• Unnamed Item
• Unnamed Item
• Closed factorization
• A subquadratic algorithm for minimum palindromic factorization
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Computing runs on a general alphabet
• Lempel-Ziv factorization using less time \& space
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• On Prefix/Suffix-Square Free Words
• Towards a Solution to the “Runs” Conjecture
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Diverse Palindromic Factorization is NP-Complete
• Palindromic length in linear time
• Computing Palindromic Factorizations and Palindromic Covers On-line
• The “Runs” Theorem
• Faster Longest Common Extension Queries in Strings over General Alphabets
• Factorizing a String into Squares in Linear Time
• Free differential calculus. IV: The quotient groups of the lower central series

This page was built for publication: On the size of overlapping Lempel-Ziv and Lyndon factorizations