On the complexity of the smallest grammar problem over fixed alphabets
DOI10.1007/s00224-020-10013-wzbMath1464.68100OpenAlexW3098381330MaRDI QIDQ2035481
Benjamin Gras, Henning Fernau, Markus L. Schmid, Serge Gaspers, Katrin Casel
Publication date: 24 June 2021
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-020-10013-w
NP-completenessstraight-line programsgrammar-based compressionsmallest grammar problemexact exponential-time algorithms
Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- A bisection algorithm for grammar-based compression of ordered trees
- Searching for smallest grammars on large sequences and application to DNA
- Parameter reduction and automata evaluation for grammar-compressed trees
- On the grammatical complexity of finite languages
- \(\Delta \)-list vertex coloring in linear time
- The complexity of tree automata and XPath on grammar-compressed trees
- A lower-bound for the number of productions required for a certain class of languages
- Concise description of finite languages
- Independent domination in chordal graphs
- Some simplified NP-complete graph problems
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Some APX-completeness results for cubic graphs
- On minimal grammar problems for finite languages
- The smallest grammar problem revisited
- On the complexity of pattern matching for highly compressed two-dimensional texts.
- Fast algorithms for min independent dominating set
- Lower bounds for context-free grammars
- Parametrized complexity theory.
- Algorithmics on SLP-compressed strings: A survey
- Recompression
- The Smallest Grammar Problem
- Unification with Singleton Tree Grammars
- Data compression via textual substitution
- Extremal Values of the Interval Number of a Graph
- Compression of individual sequences via variable-rate coding
- Efficient Generation of Minimal Length Addition Chains
- Universal lossless compression via multilevel pattern matching
- Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
- Grammar-based codes: a new class of universal lossless source codes
- The Compressed Word Problem for Groups
- Compressibility of Finite Languages by Grammars
- Parameterized Algorithms
- A Theorem on Coloring the Lines of a Network
- Theory and Applications of Models of Computation
- Grammar-based compression of unranked trees
This page was built for publication: On the complexity of the smallest grammar problem over fixed alphabets
