Interested Article - Задача о наименьшей грамматике
lauretta
- 2021-02-26
- 1
В теории формальных языков задачей о наименьшей грамматике называется задача нахождения наименьшей контекстно-свободной грамматики , которая порождает уникальную последовательность символов. Размер грамматики частью авторов определяется числом символов в правой части правил вывода. Но иногда включается и число правил.
Примечания
- Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi. (англ.) // : journal. — 2005. — Vol. 51 . — P. 2554—2576 . — doi : . 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 :
Литература
- 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 // (англ.) . — New York, NY: Association for Computing Machinery , 2002. — P. 792—801. — ISBN 1-581-13495-9 . — doi : .
lauretta
- 2021-02-26
- 1
