Нижние границы размера CFG для определенных конечных языков

14

Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?LL

Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , , n } : интуитивно, CFG для L n «должен» иметь размер Ω ( п ! ) . Таким образом, нас интересует асимптотический размер самых маленьких CFG для языков.LNLN{1,...,N}LNΩ(N!)

Подобные вопросы были рассмотрены в нескольких статьях:

  • Чарикар и др. («Аппроксимация наименьшей грамматики: сложность Колмогорова в естественных моделях») рассмотрим, насколько трудно приблизиться к размеру наименьшего CFG, порождающего данное слово .
  • Больше работы в этом направлении - Арпе и Рейщук, «О сложности оптимального сжатия на основе грамматики».
  • У Питера Асвельда есть несколько работ на эту тему (например, «Генерация всех перестановок с помощью контекстно-свободных грамматик в нормальной форме Хомского»). Он пытается оптимизировать некоторые параметры на определенных типах грамматик, генерирующих множество всех перестановок, в частности нормальных форм Хомского и Грейбаха.

Ω(N!)LN

Существуют ли статьи, предоставляющие нижние оценки для размера контекстно-свободных грамматик для конкретных конечных языков?

LN

Юваль Фильмус
источник
(предыдущий комментарий относится к удаленному вопросу). сформулировал эту проблему сжатия так , чтобы она могла быть очень актуальной или полезной при доказательстве нижних границ по сравнению со сжатием cfg, возможно, с помощью методов диагонализации & (также может быть связана со сложностью Колмогорова).
vzn
См. Связанный вопрос cstheory.stackexchange.com/q/4962
Андраш Саламон

Ответы:

11

Добрый рецензент прислал мне бумагу, которая доказывает точно такую ​​же нижнюю границу, как и я, точно таким же образом. Бумага

К. Эллул, Б. Кравец, Дж. Шаллит, М.-В. Ван, Регулярные выражения: новые результаты и открытые проблемы , J. Autom. Lang. Гребень. 10 (2005), 407–432.

Результатом является теорема 30 в статье.

Юваль Фильмус
источник
Препринт статьи находится по адресу cs.uwaterloo.ca/~shallit/Papers/re3.pdf
Саламон,