On the complexity of the smallest grammar problem over fixed alphabets

DOI10.1007/s00224-020-10013-wzbMath1464.68100MaRDI QIDQ2035481

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

Publication date: 24 June 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-10013-w

zbMATH Keywords

NP-completeness; straight-line programs; grammar-based compression; smallest grammar problem; exact exponential-time algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

68Q42: Grammars and rewriting systems

Uses Software

• TreeRePair