Publication:4598264
From MaRDI portal
DOI10.4230/LIPIcs.ICALP.2016.122zbMath1388.68036MaRDI QIDQ4598264
Henning Fernau, Serge Gaspers, Markus L. Schmid, Katrin Casel, Benjamin Gras
Publication date: 19 December 2017
NP-completeness; straight-line programs; grammar-based compression; exact exponential time algorithms
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68Q42: Grammars and rewriting systems
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures