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