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

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)