Algorithmics on SLP-compressed strings: A survey

DOI10.1515/GCC-2012-0016zbMath1285.68088OpenAlexW2052653988MaRDI QIDQ2874365

Markus Lohrey

Publication date: 30 January 2014

Published in: Groups - Complexity - Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/gcc-2012-0016

zbMATH Keywords

computational complexityalgorithms for compressed stringscompressed word problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Formal languages and automata (68Q45) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algorithms on strings (68W32)

Related Items (46)

XML compression via directed acyclic graphs ⋮ On the Balancedness of Tree-to-Word Transducers ⋮ Equality Testing of Compressed Strings ⋮ Compressed Tree Canonization ⋮ Grammar-Based Tree Compression ⋮ Approximating LZ77 via Small-Space Multiple-Pattern Matching ⋮ Unnamed Item ⋮ Approximation of smallest linear tree grammar ⋮ Evaluating Matrix Circuits ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Processing succinct matrices and vectors ⋮ Parallel Identity Testing for Skew Circuits with Big Powers and Applications ⋮ Linear pattern matching of compressed terms and polynomial rewriting ⋮ Logspace and compressed-word computations in nilpotent groups ⋮ The fully compressed subgroup membership problem ⋮ Unnamed Item ⋮ On Arch Factorization and Subword Universality for Words and Compressed Words ⋮ A \textit{really} simple approximation of smallest grammar ⋮ Knapsack in graph groups ⋮ On the compressibility of finite languages and formal proofs ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Approximation of grammar-based compression via recompression ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ The complexity of compressed membership problems for finite automata ⋮ Compaction of Church numerals ⋮ Grammar-based compression of unranked trees ⋮ Unnamed Item ⋮ Constant-time tree traversal and subtree equality check for grammar-compressed trees ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Inter-procedural Two-Variable Herbrand Equalities ⋮ Complexity of word problems for HNN-extensions ⋮ Low-complexity computations for nilpotent subgroup problems ⋮ Logspace computations in graph products ⋮ Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ Compressibility of Finite Languages by Grammars ⋮ SLP compression for solutions of equations with constraints in free and hyperbolic groups ⋮ Random Access to High-Order Entropy Compressed Text ⋮ Approximate pattern matching in LZ77-compressed texts ⋮ Balancing straight-line programs for strings and trees ⋮ Tree compression with top trees ⋮ Fast distance multiplication of unit-Monge matrices ⋮ On the Balancedness of Tree-to-Word Transducers ⋮ Online LZ77 Parsing and Matching Statistics with RLBWTs ⋮ Compression techniques in group theory

This page was built for publication: Algorithmics on SLP-compressed strings: A survey