Approximating the smallest grammar
From MaRDI portal
Publication:3579221
DOI10.1145/509907.510021zbMath1192.68397OpenAlexW1979254690MaRDI QIDQ3579221
Eric Lehman, Panigrahy Rina, Amit Sahai, Manoj Prabhakaran, Ding Liu, Abhi Shelat, April Rasala, Moses Charikar
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.510021
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Grammars and rewriting systems (68Q42)
Related Items
A circuit complexity formulation of algorithmic information theory ⋮ Application of Lempel-Ziv factorization to the approximation of grammar-based compression. ⋮ Generalized substring compression ⋮ Finite state complexity ⋮ Learning grammars for architecture-specific facade parsing ⋮ One-Dimensional Staged Self-assembly ⋮ A fully linear-time approximation algorithm for grammar-based compression ⋮ One-dimensional staged self-assembly ⋮ Finite state incompressible infinite sequences