Approximating the smallest grammar
From MaRDI portal
Publication:3579221
DOI10.1145/509907.510021zbMath1192.68397MaRDI 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
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68Q42: Grammars and rewriting systems
Related Items
One-dimensional staged self-assembly, Finite state incompressible infinite sequences, Finite state complexity, Application of Lempel-Ziv factorization to the approximation of grammar-based compression., Learning grammars for architecture-specific facade parsing, Generalized substring compression, A fully linear-time approximation algorithm for grammar-based compression, One-Dimensional Staged Self-assembly