Lyndon factorization of grammar compressed texts revisited

DOI10.4230/LIPICS.CPM.2018.24zbMath1497.68601OpenAlexW2803338549MaRDI QIDQ5140789

Hideo Bannai, Masayuki Takeda, Yuto Nakashima, Isamu Furuya, Shunsuke Inenaga, Tomohiro I.

Publication date: 16 December 2020

Full work available at URL: http://doi.org/10.4230/LIPIcs.CPM.2018.24

zbMATH Keywords

Lyndon wordLyndon factorizationstraightline program

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Uses Software

• LZ77

Cites Work

• Unnamed Item
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Lyndon + Christoffel = digitally convex
• Parallel RAM algorithms for factorizing words
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Factorizing words over an ordered alphabet
• The Smallest Grammar Problem
• Fast parallel Lyndon factorization with applications
• Efficient Lyndon Factorization of Grammar Compressed Text
• Longest Common Extensions with Recompression.
• Minimal Suffix and Rotation of a Substring in Optimal Time
• Free differential calculus. IV: The quotient groups of the lower central series

This page was built for publication: Lyndon factorization of grammar compressed texts revisited