Параметризованная сложность включения обычных языков

11

Меня интересует классическая проблема РЕГУЛЯРНОГО ВКЛЮЧЕНИЯ ЯЗЫКА. Для регулярного выражения обозначим через L ( E ) связанный с ним регулярный язык. (Регулярные выражения на фиксированном алфавите Σ с объединением операций, звездой Клини и конкатенацией.)ЕL(Е)Σ

Входные данные: два регулярных выражения и E 2 Вопрос: Верно ли, что L ( E 1 ) L ( E 2 ) ?Е1Е2
L(Е1)L(Е2)

Известно, что РЕГУЛЯРНОЕ ВКЛЮЧЕНИЕ ЯЗЫКА является PSPACE-полным [1].

Классический способ ее решения (в PSPACE) состоит в том, чтобы создать NFA и A 2, связанные с E 1 и E 2 , построить DFA D 2 из A 2 , дополнить его в DFA D C 2 и, наконец, построить автомат пересечения A P из A 1 и D C 2, соответствующий пересечению L ( E 1 ) и L ( E 2 ) CA1A2Е1Е2D2A2D2СAпA1D2СL(Е1)L(Е2)С, Теперь тогда и только тогда, когда в A P нет принимающего пути .L(Е1)L(Е2)Aп

Если я не ошибаюсь, весь процесс может быть выполнен за полиномиальное время, когда является фиксированным языком, поскольку единственное экспоненциальное увеличение происходит от преобразования A 2 в D 2 . Еще лучше проблема заключается в FPT при параметризации | Е 2 | длина Е 2 .Е2A2D2|Е2|Е2

Это мотивирует мой вопрос:

Вопрос: Когда является фиксированным выражением, какова сложность REGULAR LANGUAGE INCLUSION? Это остается PSPACE-полным?Е1

[1] Л.Дж. Стокмейер и А.Р. Мейер. Проблемы со словами, требующие экспоненциального времени: предварительный отчет. Материалы пятого ежегодного симпозиума ACM по теории вычислений, STOC '73, стр. 1-9.

Замечание: будучи не экспертом в этой области, я нахожу [1] (и связанные с ним статьи того времени) совершенно нечитабельным и не смог найти другого доказательства полноты PSPACE - любого указателя на современное доказательство, такого как в книга, очень приветствуется! Кроме того, авторы, кажется, допускают возведение в квадрат в своих регулярных выражениях, что, на мой взгляд, в настоящее время довольно нестандартно.)

Флоран Фуко
источник
4
Он остается PSPACE-полным, так как универсальность языка (т.е. E1 = Sigma *) является PSPACE-полной.
Денис
3
Кстати, разрешение квадратов делает задачу EXPSPACE-полной, упомянутые вами результаты без квадратов.
Денис
1
Для , то разрешимо в постоянная время. Для E 1 = w для фиксированной строки w она разрешима за полиномиальное время. Для E 1 = Σ оно является PSPACE-полным. Существует ли E 1 такой, что проблема является N P -полной? Е1знак равноЕ1знак равновесвесЕ1знак равноΣ*Е1Nп
Майкл Вехар
2
Хорошо спасибо! @ Денис, пожалуйста, включите ответ (со ссылкой), и я приму это!
Флоран Фуко,
3
@MichaelWehar: некоторые случаи, полные coNP, доказаны здесь ( doi.org/10.1137/080743457 ), но они не для фиксированных языков (но для очень ограниченных классов языков)
Флорент Фуко,

Ответы:

14

Частный случай универсальности языка (все ли слова приняты?) Является PSPACE-полным для регулярных выражений или NFA. Он отвечает на ваш вопрос: в общем случае задача остается PSPACE-полной даже для фиксированного , поскольку универсальность языка соответствует E 1 = Σ .Е1Е1знак равноΣ*

Действительно трудно найти современное удобочитаемое доказательство твердости PSPACE для универсальности регулярных выражений, поскольку теперь это считается фольклором. Вот схема быстрого доказательства, которая позволяет перестроить доказательство:


Рассмотрим машину Тьюринга на алфавите Е с использованием полиномиального пространства р ( п ) , и пусть W Е * входное слово для M . Мы построим регулярное выражение e, которое принимает все слова в том и только в том случае, если M не принимает прогон на w .MΣп(N)весΣ*MеMвес

Рассмотрим язык состоящий из слов вида $ C 0 $ C 1 $ $ C f $ , где каждый C i является конфигурацией M длины ровно p ( n ) , C 0 является начальной конфигурацией с w на лента, С F принимает, и каждый из С яС я + 1 является допустимым переход М . Слово в LLM$С0$С1$...$Се$СяMп(N)С0весСеСяСя+1M описывает принимающую пробег M .LMM

Мы строим на алфавите Х ' = Е { $ } такие , что е принимает именно те слова, которые не в L M , посмотрев за нарушение определения L M . Выражение e будет большой дизъюнкцией e 1 + e 2 + + e k , где каждый e i ищет различный вид нарушения. Например, e 1 = ( Σ ) $еΣ'знак равноΣ{$}еLMLMее1+е2++еКея ищет нарушение того факта, что каждый C i имеет размер ровно p ( n ) . Самая сложная часть - угадать нарушение между C i и C i + 1 : выражение может сравнивать локальный шаблон в C i и его изображение в C i + 1 , используя t

e1=(Σ)$(Σ<p(n)+Σ>p(n))$(Σ)
Cip(n)CiCi+1CiCi+1 , где t и t - выражения для локальных шаблонов. При этом мы можем угадать нарушение функции перехода M на локальном шаблоне или нарушение тождества вне этого шаблона. В конце концов, мы получаемчто L ( е ) ( Σ ' ) *  тогда и только тогда , когда  L M тогда и только тогда , когда  M  принимает  шT(Σ')п(N)T'TT'M
L(е)(Σ')* если и только если LM если и только если M принимает вес
поэтому мы сводили (полиномиально) произвольную задачу PSPACE к универсальности регулярного выражения. Я пропустил некоторые детали, но это должно позволить вам создать полное доказательство.

Конечно, как отметил Майкл Вехар в комментариях, для других проблема может стать проще. Классификация сложности этой проблемы широко изучалась в этой статье [1] на предмет эквивалентности, локализации и покрытия. Вы можете увидеть сводку результатов для проблемы эквивалентности в этом ответе (существуют NP-полные случаи).Е1

(Σ')п(N)п(N)п(N)

[1] Об эквивалентности, содержании и проблемах покрытия для регулярных и контекстно-свободных языков Гарри Б. Хант, Даниэль Дж. Розенкранц, Томас Г. Шимански. Журнал компьютерных и системных наук. Том 12, выпуск 2, апрель 1976 года, страницы 222-268

[2] Проблема эквивалентности для регулярных выражений с возведением в квадрат требует экспоненциального пространства . Мейер, AR и Л. Стокмейер. 13-й симпозиум IEEE по теории коммутации и автоматов, октябрь 1972 г., с. 125–129.

Денис
источник
Вау, большое спасибо за то, что поделились ссылками !! Это аккуратно !! :)
Майкл Вехар
2
Мой коллега указал мне на следующий опрос, который посвящен этому типу проблем с обычным языком и автоматами и содержит дополнительные полезные ссылки: sciencedirect.com/science/article/pii/S0890540110001999
Флоран Фуко