Smallest grammar problem
From HandWiki
In data compression and the theory of formal languages, the smallest grammar problem is the problem of finding the smallest context-free grammar that generates a given string of characters (but no other string). The size of a grammar is defined by some authors as the number of symbols on the right side of the production rules.[1] Others also add the number of rules to that.[2] The (decision version of the) problem is NP-complete.[1] The smallest context-free grammar that generates a given string is always a straight-line grammar without useless rules.[citation needed]
See also
- Grammar-based code
- Kolmogorov Complexity
- Lossless data compression
References
- ↑ 1.0 1.1 Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi (2005). "The Smallest Grammar Problem". IEEE Transactions on Information Theory 51 (7): 2554–2576. doi:10.1109/TIT.2005.850116. http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf.
- ↑ Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceedings of the fifteenth annual conference on Genetic and evolutionary computation conference - GECCO ’13, 2013. ISBN 978-1-4503-1963-8 doi:10.1145/2463372.2463441
- Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Rasala, April; Sahai, Amit; Shelat, Abhi (2002). "Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models". Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press. pp. 792–801. doi:10.1145/509907.510021. ISBN 978-1-581-13495-7. http://theory.lcs.mit.edu/~arasala/papers/grammar.pdf.
 |  |
