On the complexity of the smallest grammar problem over fixed alphabets
DOI10.1007/S00224-020-10013-WzbMATH Open1464.68100OpenAlexW3098381330MaRDI QIDQ2035481FDOQ2035481
Authors: Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid 
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
Recommendations
NP-completenessgrammar-based compressionstraight-line programssmallest 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)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some APX-completeness results for cubic graphs
- Title not available (Why is that?)
- Universal lossless compression via multilevel pattern matching
- Title not available (Why is that?)
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Parametrized complexity theory.
- Title not available (Why is that?)
- Compression of individual sequences via variable-rate coding
- Title not available (Why is that?)
- Parameterized Algorithms
- Some simplified NP-complete graph problems
- Algorithmics on SLP-compressed strings: a survey
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parameter reduction and automata evaluation for grammar-compressed trees
- The complexity of tree automata and XPath on grammar-compressed trees
- Title not available (Why is that?)
- Lower bounds for context-free grammars
- A Theorem on Coloring the Lines of a Network
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Fast algorithms for min independent dominating set
- Recompression
- The Smallest Grammar Problem
- A bisection algorithm for grammar-based compression of ordered trees
- Independent domination in chordal graphs
- Data compression via textual substitution
- Grammar-based codes: a new class of universal lossless source codes
- Searching for smallest grammars on large sequences and application to DNA
- On the complexity of pattern matching for highly compressed two-dimensional texts.
- Unification with Singleton Tree Grammars
- Grammar-based compression of unranked trees
- Title not available (Why is that?)
- Extremal Values of the Interval Number of a Graph
- Efficient Generation of Minimal Length Addition Chains
- \(\Delta \)-list vertex coloring in linear time
- Theory and Applications of Models of Computation
- Title not available (Why is that?)
- On the grammatical complexity of finite languages
- Concise description of finite languages
- A lower-bound for the number of productions required for a certain class of languages
- On minimal grammar problems for finite languages
- The smallest grammar problem revisited
- The Compressed Word Problem for Groups
- Compressibility of Finite Languages by Grammars
- Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
Cited In (4)
Uses Software
This page was built for publication: On the complexity of the smallest grammar problem over fixed alphabets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035481)
