The Smallest Grammar Problem
From MaRDI portal
Recommendations
Cited in
(98)- Random access in persistent strings and segment selection
- On the complexity of grammar-based compression over fixed alphabets
- Finger search in grammar-compressed strings
- Grammar-Based Tree Compression
- scientific article; zbMATH DE number 2087040 (Why is no real title available?)
- scientific article; zbMATH DE number 2119662 (Why is no real title available?)
- Compact q-gram profiling of compressed strings
- Balancing straight-line programs for strings and trees
- Upper bounds on distinct maximal (sub-)repetitions in compressed strings
- Finding the smallest binarization of a CFG is NP-hard
- Equality Testing of Compressed Strings
- Tree compression with top trees
- Variable-length coding of two-sided asymptotically mean stationary measures
- Block trees
- Constructing small tree grammars and small circuits for formulas
- Access, rank, and select in grammar-compressed strings
- Approximate pattern matching in LZ77-compressed texts
- The smallest grammar problem as constituents choice and minimal grammar parsing
- Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
- Searching for smallest grammars on large sequences and application to DNA
- Parameter reduction and automata evaluation for grammar-compressed trees
- Compaction of Church numerals
- Grammar compressed sequences with rank/select support
- Repetitiveness measures based on string morphisms
- Leaf languages and string compression
- Comparison of LZ77-type parsings
- Block graphs in practice
- Cadences in grammar-compressed strings
- The complexity of tree automata and XPath on grammar-compressed trees
- Knapsack in graph groups
- Constant-time tree traversal and subtree equality check for grammar-compressed trees
- LZ77 computation based on the run-length encoded BWT
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Grammar-based compression and its use in symbolic music analysis
- A separation between RLSLPs and LZ77
- Document listing on repetitive collections with guaranteed performance
- Generalized straight-line programs
- The smallest grammar problem revisited
- Computing MEMs and relatives on repetitive text collections
- Lyndon factorization of grammar compressed texts revisited
- An LMS-based grammar self-index with local consistency properties
- On the complexity of the smallest grammar problem over fixed alphabets
- Universal coding and prediction on ergodic random points
- Choosing word occurrences for the smallest grammar problem
- Generalization of repetitiveness measures for two-dimensional strings
- Compressed decision problems in hyperbolic groups
- The compressed word problem in relatively hyperbolic groups
- String search experimentation using massive data
- The complexity of compressed membership problems for finite automata
- Approximability of minimum AND-circuits
- A really simple approximation of smallest grammar
- String Indexing with Compressed Patterns
- Random access to grammar-compressed strings and trees
- Random access to high-order entropy compressed text
- Relations between greedy and bit-optimal LZ77 encodings
- Grammar-compressed indexes with logarithmic search time
- Compression techniques in group theory
- Linear-size suffix tries and linear-size CDAWGs simplified and improved
- A textbook solution for dynamic strings
- On the approximation ratio of LZ-end to LZ77
- Self-indexed Text Compression Using Straight-Line Programs
- Compressibility of Finite Languages by Grammars
- Approximation of smallest linear tree grammar
- A bisection algorithm for grammar-based compression of ordered trees
- Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover
- Lower bounds for context-free grammars
- Learning grammars for architecture-specific facade parsing
- Approximation of grammar-based compression via recompression
- On pumping constants and smallest grammars for context-free languages
- Excess entropy in natural language: present state and perspectives
- Inductive synthesis of cover-grammars with the help of ant colony optimization
- Bat-LZ out of hell
- Binary jumbled pattern matching on trees and tree-like structures
- scientific article; zbMATH DE number 7559146 (Why is no real title available?)
- scientific article; zbMATH DE number 7561757 (Why is no real title available?)
- Compressed tree canonization
- A \textit{really} simple approximation of smallest grammar
- Sensitivity of string compressors and repetitiveness measures
- scientific article; zbMATH DE number 7765406 (Why is no real title available?)
- Time-space trade-offs for Lempel-Ziv compressed indexing
- scientific article; zbMATH DE number 7559179 (Why is no real title available?)
- Balancing run-length straight-line programs
- On two LZ78-style grammars: compression bounds and compressed-space computation
- On the compressibility of finite languages and formal proofs
- Straight-line programs: a practical test (extended abstract)
- Universal compressed text indexing
- Approximation ratios of \textsf{RePair}, \textsf{LongestMatch} and \textsf{Greedy} on unary strings
- Rpair: rescaling RePair with Rsync
- scientific article; zbMATH DE number 4166865 (Why is no real title available?)
- scientific article; zbMATH DE number 7559186 (Why is no real title available?)
- A self-index on block trees
- A simple grammar-based index for finding approximately longest common substrings
- Computing all-vs-all MEMs in grammar-compressed text
- Sublinear time Lempel-Ziv (LZ77) factorization
- Iterated straight-line programs
- Space-efficient conversions from SLPs
- Lazy Lempel-Ziv factorization algorithms
- Functional programs as compressed data
This page was built for publication: The Smallest Grammar Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546682)
