Самая маленькая грамматическая проблема

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

Каждая двоичная строка длины имеет грамматику длины , выраженную с помощью нотации O большое . ^[3] Для двоичных последовательностей де Брейна лучшая длина невозможна. ^[4] ${\displaystyle n}$ ${\displaystyle O(n/\log n)}$

(Версия решения) наименьшей грамматической задачи является NP-полной . ^[1] Она может быть аппроксимирована за полиномиальное время с точностью до логарифмического отношения аппроксимации ; точнее, отношение равно , где — длина заданной строки, а — размер ее наименьшей грамматики. Ее трудно аппроксимировать с точностью до постоянного отношения аппроксимации. Улучшение отношения аппроксимации до также улучшило бы некоторые алгоритмы для приближенных цепочек сложения . ^[5] ${\displaystyle O(\log {\tfrac {n}{g}})}$ ${\displaystyle n}$ ${\displaystyle g}$ ${\displaystyle o(\log n/\log \log n)}$

Смотрите также

• Грамматический код
• сложность Колмогорова
• Сжатие данных без потерь

Ссылки

1. Чарикар, Моисей; Леман, Эрик; Лю, Дин; Паниграхи, Рина; Прабхакаран, Манодж; Сахай, Амит; Шелат, Абхи (2005). «Маленькая грамматическая задача». Транзакции IEEE по теории информации . 51 (7): 2554–2576. CiteSeerX  10.1.1.185.2130 . дои : 10.1109/TIT.2005.850116. S2CID  6900082. Збл  1296.68086.
2. Флориан Бенц и Тимо Кётцинг, «Эффективная эвристика для наименьшей грамматической проблемы», Труды пятнадцатой ежегодной конференции по генетическим и эволюционным вычислениям - GECCO '13, 2013. ISBN 978-1-4503-1963-8 doi :10.1145/2463372.2463441 
3. Lohrey, Markus (2012). "Алгоритмика на сжатых SLP строках: обзор" (PDF) . Groups Complexity Cryptology . 4 (2): 241–299. doi :10.1515/GCC-2012-0016.
4. Домарацки, Майкл; Пигиццини, Джованни; Шаллит, Джеффри (2002). «Моделирование конечных автоматов с помощью контекстно-свободных грамматик». Information Processing Letters . 84 (6): 339–344. doi :10.1016/S0020-0190(02)00316-2. MR  1937222.
5. Чарикар, Моисей; Леман, Эрик; Лю, Дин; Паниграхи, Рина; Прабхакаран, Манодж; Расала, Эйприл; Сахай, Амит; Шелат, Абхи (2002). «Аппроксимация наименьшей грамматики: сложность Колмогорова в естественных моделях» (PDF) . Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений (STOC 2002), Монреаль, Квебек, Канада, 19–21 мая 2002 г. Нью-Йорк, Нью-Йорк: ACM Press. стр. 792–801. doi :10.1145/509907.510021. ISBN 978-1-581-13495-7. S2CID  282489. Збл  1192,68397.

Внешние ссылки

• «CFG-Kolm-complexity — это одноэлементные множества с Лэнсом и Биллом». Computational Complexity . 9 июня 2024 г.