Efficient Lyndon factorization of grammar compressed text

DOI10.1007/978-3-642-38905-4_16zbMATH Open1381.68315arXiv1304.7061OpenAlexW1672321586MaRDI QIDQ4928569FDOQ4928569

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)

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.

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

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

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)

Cited In (7)

• 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
• Lyndon factorization algorithms for small alphabets and run-length encoded strings

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)