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
• Lyndon factorization of grammar compressed texts revisited
• Efficient LZ78 factorization of grammar compressed text
• Necklaces and bracelets in R
• On two LZ78-style grammars: compression bounds and compressed-space computation
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• An Efficient LLL Gram Using Buffered Transformations

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)