Задача о наименьшей грамматике
 | Для улучшения этой статьи по информационным технологиям желательно:
|
В теории формальных языков задачей о наименьшей грамматике называется задача нахождения наименьшей контекстно-свободной грамматики, которая порождает уникальную последовательность символов. Размер грамматики частью авторов определяется числом символов в правой части правил вывода.[1] Но иногда включается и число правил.[2]
Примечания[править | править код]
- ↑ (2005) «The Smallest Grammar Problem». IEEE Transactions on Information Theory 51: 2554–2576. DOI:10.1109/TIT.2005.850116.
- ↑ 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. DOI:10.1145/2463372.2463441
Литература[править | править код]
- 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, 2002. — P. 792–801. — ISBN 1-581-13495-9.
