Algorithmics on SLP-compressed strings: a survey
From MaRDI portal
Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Formal languages and automata (68Q45) Algorithms on strings (68W32) Analysis of algorithms (68W40)
Recommendations
Cited in
(73)- Efficient algorithms to compute compressed longest common substrings and compressed palindromes
- Knapsack in graph groups
- On the compressibility of finite languages and formal proofs
- Evaluation of circuits over nilpotent and polycyclic groups
- Certain query answering on compressed string patterns: from streams to hyperstreams
- Compaction of Church numerals
- On the complexity of the smallest grammar problem over fixed alphabets
- Balancing straight-line programs for strings and trees
- Compression techniques in group theory
- The complexity of compressed membership problems for finite automata
- Compressed string-matching in standard Sturmian words
- Approximate pattern matching in LZ77-compressed texts
- Tree compression with top trees
- Fast distance multiplication of unit-Monge matrices
- Fast \(q\)-gram mining on SLP compressed strings
- A PTIME-complete matching problem for SLP-compressed words
- Constructing small tree grammars and small circuits for formulas
- Detecting regularities on grammar-compressed strings
- XML compression via directed acyclic graphs
- Random access to high-order entropy compressed text
- Detecting regularities on grammar-compressed strings
- Parallel identity testing for skew circuits with big powers and applications
- Compressed membership problems for regular expressions and hierarchical automata
- Leaf languages and string compression
- Evaluating matrix circuits
- Solutions to twisted word equations and equations in virtually free groups
- scientific article; zbMATH DE number 7228439 (Why is no real title available?)
- Approximation of smallest linear tree grammar
- Equality Testing of Compressed Strings
- Compressed tree canonization
- Grammar-Based Tree Compression
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- scientific article; zbMATH DE number 1490000 (Why is no real title available?)
- An efficient algorithm to test square-freeness of strings compressed by straight-line programs
- Linear pattern matching of compressed terms and polynomial rewriting
- NC algorithms for finding a maximal set of paths with application to compressing strings
- Parallel identity testing for skew circuits with big powers and applications
- Low-complexity computations for nilpotent subgroup problems
- Nominal unification with atom and context variables
- Approximation of grammar-based compression via recompression
- On the balancedness of tree-to-word transducers
- Unambiguous conjunctive grammars over a one-symbol alphabet
- Compressed decision problems in hyperbolic groups
- Logspace and compressed-word computations in nilpotent groups
- Matching of compressed patterns with character-variables
- Online LZ77 parsing and matching statistics with RLBWTs
- SLP compression for solutions of equations with constraints in free and hyperbolic groups.
- Grammatical compression: compressed equivalence and other problems
- An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs
- Computing Longest Common Substring and All Palindromes from Compressed Strings
- Compressibility of Finite Languages by Grammars
- Querying and Embedding Compressed Texts
- Logspace computations in graph products
- Complexity of word problems for HNN-extensions
- The fully compressed subgroup membership problem
- Balancing run-length straight-line programs
- On Arch Factorization and Subword Universality for Words and Compressed Words
- On the Balancedness of Tree-to-Word Transducers
- Data structures for SMEM-finding in the PBWT
- Extended formulations via decision diagrams
- Compressed decision problems in hyperbolic groups
- Directed regular and context-free languages
- Constant-delay enumeration for SLP-compressed documents
- Space-efficient SLP encoding for O( N)-time random access
- Constant-time tree traversal and subtree equality check for grammar-compressed trees
- Subsequence matching and analysis problems for formal languages
- A formal language perspective on factorized representations
- Pattern matching on run-length grammar-compressed strings in linear time
- Doubly-periodic string comparison
- FO-query enumeration over SLP-compressed structures of bounded degree
- Streaming periodicity with mismatches, wildcards, and edits
- Constant delay traversal of grammar-compressed graphs with bounded rank
- A \textit{really} simple approximation of smallest grammar
This page was built for publication: Algorithmics on SLP-compressed strings: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874365)
