Самая маленькая грамматическая задача

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

«CFG-Kolm-сложность — это одноэлементные наборы с Лэнсом и Биллом» . Вычислительная сложность . 9 июня 2024 г.

Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

[moses-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 дои : 10.1145/2463372.2463441

[lohrey-3] Перейти обратно: ^а ^б Лори, Маркус (2012). «Алгоритмика строк, сжатых с помощью SLP: обзор» (PDF) . Криптология сложности групп . 4 (2): 241–299. дои : 10.1515/GCC-2012-0016 .

[4] Домарацкий, Майкл; Пигидзини, Джованни; Шалит, Джеффри (2002). «Моделирование конечных автоматов с помощью контекстно-свободных грамматик». Письма об обработке информации . 84 (6): 339–344. дои : 10.1016/S0020-0190(02)00316-2 . МР 1937222 .

[5] Чарикар, Моисей; Леман, Эрик; Лю, Дин; Паниграхи, Рина; Прабхакаран, Манодж; Расала, апрель; Сахай, Амит; Шелат, Абхи (2002). «Аппроксимация наименьшей грамматики: колмогоровская сложность в натуральных моделях» (PDF) . Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений (STOC 2002), Монреаль, Квебек, Канада, 19–21 мая 2002 г. Нью-Йорк, штат Нью-Йорк: ACM Press. стр. 792–801. дои : 10.1145/509907.510021 . ISBN 978-1-581-13495-7 . S2CID 282489 . Збл 1192,68397 .

[1]

[2]

[3]

[4]

[5]