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

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

ПримечанияПравить

↑ Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi. The Smallest Grammar Problem (англ.) // IEEE Transactions on Information Theory (англ.) (рус. : journal. — 2005. — Vol. 51. — P. 2554—2576. — doi:10.1109/TIT.2005.850116. Архивировано 9 августа 2017 года.
↑ 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. 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: Association for Computing Machinery, 2002. — P. 792—801. — ISBN 1-581-13495-9. — doi:10.1145/509907.510021.

[moses-1] Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi. The Smallest Grammar Problem (англ.) // IEEE Transactions on Information Theory (англ.) (рус. : journal. — 2005. — Vol. 51. — P. 2554—2576. — doi:10.1109/TIT.2005.850116. Архивировано 9 августа 2017 года.

[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. ISBN 978-1-4503-1963-8 doi:10.1145/2463372.2463441

[1]

[2]