On the Complexity of Grammar-Based Compression over Fixed Alphabets

DOI10.4230/LIPIcs.ICALP.2016.122zbMath1388.68036OpenAlexW2538584224MaRDI QIDQ4598264

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

Publication date: 19 December 2017

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

zbMATH Keywords

NP-completenessstraight-line programsgrammar-based compressionexact exponential time algorithms

Mathematics Subject Classification ID

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

Related Items (3)

Approximation of smallest linear tree grammar ⋮ On the compressibility of finite languages and formal proofs ⋮ Diverse Palindromic Factorization is NP-Complete

This page was built for publication: On the Complexity of Grammar-Based Compression over Fixed Alphabets