Efficient Lyndon Factorization of Grammar Compressed Text

DOI10.1007/978-3-642-38905-4_16zbMath1381.68315arXiv1304.7061OpenAlexW1672321586MaRDI QIDQ4928569

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)

Related Items

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, Lyndon factorization algorithms for small alphabets and run-length encoded strings, Necklaces and bracelets in R, Lyndon factorization of grammar compressed texts revisited