Efficient Lyndon factorization of grammar compressed text

DOI10.1007/978-3-642-38905-4_16MaRDI QIDQ4928569zbMATH OpenOpenAlexFDO

Authors Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomohiro I

Publication date 14 June 2013

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.7061

Mathematics Subject Classification ID

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)

Abstract: We present an algorithm for computing the Lyndon factorization of a string that is given in grammar compressed form, namely, a Straight Line Program (SLP). The algorithm runs in $O(n^4+m{n}^{3}h)$ time and $O(n^2)$ space, where $m$ is the size of the Lyndon factorization, $n$ is the size of the SLP, and $h$ is the height of the derivation tree of the SLP. Since the length of the decompressed string can be exponentially large w.r.t. $n,m$ and $h$, our result is the first polynomial time solution when the string is given as SLP.

Recommendations

• Lyndon factorization of grammar compressed texts revisited
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Efficient LZ78 factorization of grammar compressed text
• Lyndon factorization algorithms for small alphabets and run-length encoded strings
• Inferring Strings from Lyndon Factorization

Cited in

(7)

• Lyndon factorization algorithms for small alphabets and run-length encoded strings
• An Efficient LLL Gram Using Buffered Transformations
• Efficient LZ78 factorization of grammar compressed text
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Lyndon factorization of grammar compressed texts revisited
• On two LZ78-style grammars: compression bounds and compressed-space computation
• Necklaces and bracelets in R

This page was built for publication: Efficient Lyndon factorization of grammar compressed text

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