On the complexity of grammar-based compression over fixed alphabets

DOI10.4230/LIPICS.ICALP.2016.122zbMATH Open1388.68036OpenAlexW2538584224MaRDI QIDQ4598264FDOQ4598264

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

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

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)

Cited In (8)

• On the complexity of the smallest grammar problem over fixed alphabets
• The complexity of compressed membership problems for finite automata
• Compressibility of Finite Languages by Grammars
• Approximation of smallest linear tree grammar
• On the compressibility of finite languages and formal proofs
• Automata, Languages and Programming
• Diverse Palindromic Factorization is NP-Complete
• 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)