Smallest grammar problem

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. 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]

References

  1. 1 2 Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi (2005). "The Smallest Grammar Problem" (PDF). IEEE Transactions on Information Theory 51 (7): 2554–2576. doi:10.1109/TIT.2005.850116. Zbl 05454194.
  2. Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceeding 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

See also

This article is issued from Wikipedia - version of the Saturday, August 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.