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

exact exponential time algorithmsgrammar-based compressionNP-completenessstraight-line programs

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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)

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

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)