On the Complexity of Grammar-Based Compression over Fixed Alphabets
On the Complexity of Grammar-Based Compression over Fixed Alphabets
复制标题
关于固定字母表上基于语法的压缩的复杂性
DOI：
10.4230/lipics.icalp.2016.122
复制
发表时间：
2016
影响因子：
7.015
通讯作者：
Markus L. Schmid
中科院分区：
文献类型：
--
作者：
Katrin Casel;H. Fernau;Serge Gaspers;Benjamin Gras;Markus L. Schmid
结果表明，如果字母表是固定的并且大小至少为 24（这解决了一个悬而未决的问题），那么最短语法问题仍然是 NP 完全问题。另一方面，如果非终结符的数量有界，则可以在多项式时间内解决该问题，这可以通过将问题编码为具有区间结构的图上的问题来表示。此外，我们提出了一种基于动态规划的 O(3n) 精确指数时间算法。对于 1 级语法，即仅起始规则包含右侧非终结符的语法，也给出了类似的结果（因此，研究“层次深度”对最短语法问题的复杂性的影响）。
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).
影响因子：
3.7
作者：
Lohrey, Markus;Maneth, Sebastian;Mennicke, Roy
通讯作者：
Mennicke, Roy