Наименьшая грамматическая проблема - Smallest grammar problem
В Сжатие данных и теория формальные языки, то самая маленькая грамматическая проблема проблема поиска наименьшего контекстно-свободная грамматика что порождает данный нить символов (но никакой другой строки). Размер грамматики определяется некоторыми авторами как количество символов в правой части правил производства.[1]Другие также добавляют к этому количество правил.[2] (Версия решения) проблема НП-полный.[1]Самая маленькая контекстно-свободная грамматика, которая генерирует данную строку, всегда прямолинейная грамматика без бесполезные правила.[нужна цитата ]
Смотрите также
Рекомендации
- ^ а б Чарикар, Моисей; Леман, Эрик; Лю, Дин; Паниграхи, Рина; Прабхакаран, Манодж; Сахай, Амит; Шелат, Абхи (2005). «Наименьшая грамматическая задача» (PDF). IEEE Transactions по теории информации. 51 (7): 2554–2576. CiteSeerX 10.1.1.185.2130. Дои:10.1109 / TIT.2005.850116. Zbl 1296.68086.
- ^ Флориан Бенц и Тимо Кётцинг, «Эффективная эвристика для решения малейшей грамматической проблемы», Материалы пятнадцатой ежегодной конференции по генетическим и эволюционным вычислениям - GECCO ’13, 2013. ISBN 978-1-4503-1963-8 Дои:10.1145/2463372.2463441
- Чарикар, Моисей; Леман, Эрик; Лю, Дин; Паниграхи, Рина; Прабхакаран, Манодж; Расала, апрель; Сахай, Амит; Шелат, Абхи (2002). «Приближение наименьшей грамматики: колмогоровская сложность в естественных моделях» (PDF). Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений (STOC 2002), Монреаль, Квебек, Канада, 19–21 мая 2002 г.. Нью-Йорк, штат Нью-Йорк: ACM Press. С. 792–801. Дои:10.1145/509907.510021. ISBN 978-1-581-13495-7. Zbl 1192.68397.
 | Этот алгоритмы или же структуры данных -связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |