Известно, что минимизация размера регулярного выражения является PSPACE-полной, даже если у нас есть DFA в качестве спецификации языка .
Каковы результаты, если язык конечен?
Можно рассмотреть эту проблему в двух моделях:
- Входные данные - это все строки в языке, и мы измеряем размер ввода как сумму длины всех строк.
- Входные данные являются DFA, и мы измеряем размер входных данных по количеству состояний DFA.
Звезда Клини бесполезна в конечном случае, поэтому только ,и (конкатенация) используются в выражении. Конечно, длина регулярного выражения кажется произвольной. Вместо этого можно дать вес каждой операции (включая добавление скобок) и попросить минимизировать вес регулярного выражения.| ⋅
Редактировать: Как отметил adrianN, это связано с грамматическими кодами. NP-Complete для создания контекстно-свободной грамматики минимальной длины для описания конечного множества. Непонятно, почему грамматика без контекста минимального размера может много значить для регулярного выражения минимального размера. Возможно, умное правило переписывания может связать эти два и доказать, что в первой модели проблема в NP.
Ответы:
Следующий аргумент по существу из ( 1 ): Варианты решения двух задач содержатся на втором уровне полиномиальной иерархии (точнее: в классе сложности ), как изложено ниже. Угадайте регулярное выражение размера не более и проверьте, эквивалентно ли оно указанному детерминированному конечному автомату (соответственно: языку, представленному в виде списка слов). kΣп2 К
Я считаю, что никаких дальнейших результатов относительно ваших проблем не известно. Для подобной задачи оптимизации, где целью является поиск минимального эквивалентного недетерминированного конечного автомата вместо регулярного выражения, известны следующие результаты:
Осторожно: в отличие от настройки бесконечных языков, я не вижу прямого сокращения от случая минимизации NFA до проблем из вашего вопроса.
Ссылки:
(1) Герман Грубер и Маркус Хольцер. Вычислительная сложность минимизации NFA для конечных и унарных языков . В: 1-я Международная конференция по теории языка и автоматов и приложений (LATA 2007), с. 261-272, 2007.
(2) Герман Грубер и Маркус Хольцер. Неподходимость недетерминированного состояния и переходная сложность в предположении P <> NP . В: 11-я Международная конференция по развитию в теории языка (DLT 2007), LNCS 4588, с. 205-216, 2007.
Редактировать: Я думаю, что грамматические коды не так тесно связаны: в этой настройке данный язык является одноэлементным набором. Но для такого одноэлементного языка регулярное выражение минимального размера (тривиально) задается .wL={w} w
источник
очевидно, не имея точного известного ответа или лучшего ответа, чем этот, вот почти / недавно ссылка на исследование, конкретно посвященное минимизации RE (что, по-видимому, необычный угол):
Минимизация NFA и регулярных выражений (2005) Грегора Грамлича, Георга Шнитгера
источник