Lyndon factorization of grammar compressed texts revisited

DOI10.4230/LIPICS.CPM.2018.24MaRDI QIDQ5140789zbMATH OpenOpenAlexFDO

Authors Isamu Furuya, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, 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)

Recommendations

• Efficient Lyndon factorization of grammar compressed text
• Efficient LZ78 factorization of grammar compressed text
• scientific article; zbMATH DE number 2087040
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• A fully linear-time approximation algorithm for grammar-based compression
• A fully linear-time approximation algorithm for grammar-based compression
• Approximation of Grammar-Based Compression via Recompression
• Approximation of grammar-based compression via recompression
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 6862137 (Why is no real title available?)
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Efficient Lyndon factorization of grammar compressed text
• Factorizing words over an ordered alphabet
• Fast parallel Lyndon factorization with applications
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Free differential calculus. IV: The quotient groups of the lower central series
• Longest common extensions with recompression
• Lyndon + Christoffel = digitally convex
• Minimal suffix and rotation of a substring in optimal time
• Parallel RAM algorithms for factorizing words
• The Smallest Grammar Problem

Cited in

(6)

• Efficient Lyndon factorization of grammar compressed text
• Inferring strings from Lyndon factorization
• Suffix array and Lyndon factorization of a text
• Efficient LZ78 factorization of grammar compressed text
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Computing minimal and maximal suffixes of a substring revisited

Describes a project that uses

Uses Software

• LZ77

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140789)