Approximating the smallest grammar: Kolmogorov complexity in natural models.

Moses Charikar, Eric P. Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai, Abhi Shelat

Browse the full STOC paper archive.