Задача о наименьшей грамматике

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории формальных языков задачей о наименьшей грамматике называется задача нахождения наименьшей контекстно-свободной грамматики, которая порождает уникальную последовательность символов. Размер грамматики частью авторов определяется числом символов в правой части правил вывода.[1] Но иногда включается и число правил.[2]

Примечания[править | править код]

  1. (2005) «The Smallest Grammar Problem». IEEE Transactions on Information Theory 51: 2554–2576. DOI:10.1109/TIT.2005.850116.
  2. 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

Литература[править | править код]