2026-07-22T11:54:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6257 2024-03-06T10:37:54Z ddc:004 open_access

On the Complexity of Grammar-Based Compression over Fixed Alphabets Casel, Katrin Fernau, Henning Gaspers, Serge Gras, Benjamin Schmid, Markus L. Grammar-Based Compression Straight-Line Programs NP-Completeness Exact Exponential Time Algorithms It is shown that the shortest-grammar problem remains NP-complete if the alphabet is fixed and has a size of at least 24 (which settles an open question). On the other hand, this problem can be solved in polynomial-time, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Furthermore, we present an O(3n) exact exponential-time algorithm, based on dynamic programming. Similar results are also given for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side (thus, investigating the impact of the "hierarchical depth" on the complexity of the shortest-grammar problem). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Katrin Casel and Henning Fernau and Serge Gaspers and Benjamin Gras and Markus L. Schmid 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.122 urn:nbn:de:0030-drops-62570 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.122 eng https://creativecommons.org/licenses/by/3.0/legalcode