On the complexity of grammar-based compression over fixed alphabets

DOI10.4230/LIPICS.ICALP.2016.122MaRDI QIDQ4598264zbMATH OpenOpenAlexFDO

Authors Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid

Publication date 19 December 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.ICALP.2016.122

zbMATH Keywords

NP-completenessgrammar-based compressionstraight-line programsexact exponential time algorithms

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Recommendations

• On the complexity of the smallest grammar problem over fixed alphabets
• The Smallest Grammar Problem
• scientific article; zbMATH DE number 2119662
• The smallest grammar problem revisited
• String Processing and Information Retrieval

Cited in

(8)

• Automata, Languages and Programming
• Compressibility of Finite Languages by Grammars
• Approximation of smallest linear tree grammar
• On the complexity of the smallest grammar problem over fixed alphabets
• The complexity of compressed membership problems for finite automata
• Diverse Palindromic Factorization is NP-Complete
• On the compressibility of finite languages and formal proofs
• Approximation of Grammar-Based Compression via Recompression

This page was built for publication: On the complexity of grammar-based compression over fixed alphabets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598264)