минимизация размера регулярного выражения для конечных множеств

15

Известно, что минимизация размера регулярного выражения является PSPACE-полной, даже если у нас есть DFA в качестве спецификации языка .

Каковы результаты, если язык конечен?

Можно рассмотреть эту проблему в двух моделях:

  1. Входные данные - это все строки в языке, и мы измеряем размер ввода как сумму длины всех строк.
  2. Входные данные являются DFA, и мы измеряем размер входных данных по количеству состояний DFA.

Звезда Клини бесполезна в конечном случае, поэтому только ,и (конкатенация) используются в выражении. Конечно, длина регулярного выражения кажется произвольной. Вместо этого можно дать вес каждой операции (включая добавление скобок) и попросить минимизировать вес регулярного выражения.| ()|

Редактировать: Как отметил adrianN, это связано с грамматическими кодами. NP-Complete для создания контекстно-свободной грамматики минимальной длины для описания конечного множества. Непонятно, почему грамматика без контекста минимального размера может много значить для регулярного выражения минимального размера. Возможно, умное правило переписывания может связать эти два и доказать, что в первой модели проблема в NP.

Чао Сюй
источник
3
Это похоже на грамматические коды .
adrianN
Предположим, размер ввода ограничен. тогда Клини Стар может быть действительной. поэтому имеет смысл определить, ограничен ли (естественно) размер ввода самой длинной строкой в ​​конечном языке. и также, если в этом случае все еще исключена клини звезда. Кроме того, в качестве (очевидной?) эвристики минимизация DFA и построение RE из этого является одной стратегией ... также обратите внимание, что RE (с заменой переменных) имеют DAG-подобную структуру и не так много (сильных) известных о минимизации DAG-подобных структур .... RE без подстановки переменных древовидны (формулы) и с ними легче работать ....
vzn
другой угол. Известно, что «производные» RE, введенные Бжозовским, полезны для преобразования RE непосредственно в DFA, см., Например, производные регулярного выражения, пересмотренные Owens, Reppy, Turon. может быть, есть какой-то способ использовать ту же структуру для обратной задачи. во всяком случае, хотя в целом это кажется открытой проблемой ....
vzn

Ответы:

4

Следующий аргумент по существу из ( 1 ): Варианты решения двух задач содержатся на втором уровне полиномиальной иерархии (точнее: в классе сложности ), как изложено ниже. Угадайте регулярное выражение размера не более и проверьте, эквивалентно ли оно указанному детерминированному конечному автомату (соответственно: языку, представленному в виде списка слов). kΣ2Pk

Я считаю, что никаких дальнейших результатов относительно ваших проблем не известно. Для подобной задачи оптимизации, где целью является поиск минимального эквивалентного недетерминированного конечного автомата вместо регулярного выражения, известны следующие результаты:

  • Для ввода, описанного как DFA, минимальная эквивалентная проблема NFA является -hard, см. ( 1 ). Здесь означает «разность полиномиального времени»; это класс сложности "Sigma" на втором уровне логической иерархии .Д ПDPDP
  • Для ввода, описанного в виде списка слов, минимальная эквивалентная задача NFA - -hard, см. ( 2 ).NP
  • Для и входных данных, описанных как таблица истинности, минимальная эквивалентная задача NFA является -полной, см. ( 2 ).N PL{0,1}mNP

Осторожно: в отличие от настройки бесконечных языков, я не вижу прямого сокращения от случая минимизации NFA до проблем из вашего вопроса.

Ссылки:

(1) Герман Грубер и Маркус Хольцер. Вычислительная сложность минимизации NFA для конечных и унарных языков . В: 1-я Международная конференция по теории языка и автоматов и приложений (LATA 2007), с. 261-272, 2007.

(2) Герман Грубер и Маркус Хольцер. Неподходимость недетерминированного состояния и переходная сложность в предположении P <> NP . В: 11-я Международная конференция по развитию в теории языка (DLT 2007), LNCS 4588, с. 205-216, 2007.

Редактировать: Я думаю, что грамматические коды не так тесно связаны: в этой настройке данный язык является одноэлементным набором. Но для такого одноэлементного языка регулярное выражение минимального размера (тривиально) задается .wL={w}w

Герман Грубер
источник
-6

очевидно, не имея точного известного ответа или лучшего ответа, чем этот, вот почти / недавно ссылка на исследование, конкретно посвященное минимизации RE (что, по-видимому, необычный угол):

Минимизация NFA и регулярных выражений (2005) Грегора Грамлича, Георга Шнитгера

Мы показываем результаты неприемлемости, касающиеся минимизации недетерминированных конечных автоматов (nfa's), а также регулярных выражений относительно заданных nfa's, регулярных выражений или детерминированных конечных автоматов (dfa's). Мы показываем, что невозможно эффективно минимизировать заданное nfa или регулярное выражение с n состояниями, переходами и т. Д. символы в пределах коэффициента o (n), если P = PSPACE. Наши результаты недопустимости для данного dfa с n состояниями основаны на криптографических предположениях, и мы показываем, что любой эффективный алгоритм будет иметь коэффициент аппроксимации по крайней мере poly (log n). Наша установка также позволяет нам анализировать минимальную непротиворечивую проблему dfa.

ВЗН
источник
4
Этот вопрос был задан именно потому, что в этой статье не рассматривается, что происходит, когда язык ограничен.
Чао Сюй
1
хорошо, тогда это служит [релевантным / nec] BKG. но обратите внимание, что если на другой вопрос нет [опубликованного] ответа, то это, конечно, не удивительно, что и этот вопрос тоже не так, близкий вариант угла может не сильно помочь. также [ mea culpa ] не заметил, что MdB цитирует статью по другому вопросу.
2013 года