Для каких регулярных выражений

21

Хорошо известно, что следующая проблема является PSPACE-полной:

Учитывая регулярное выражение , ?L ( β ) = Σ βL(β)=Σ

Как насчет определения эквивалентности другим (фиксированным) регулярным выражениям ?α

Учитывая регулярное выражение , ?L ( β ) = L ( α )βL(β)=L(α)

Известно следующее:

  • Для проблема является PSPACE-полнойα=(0+1)

  • Для или, в более общем случае, который описывает конечное множество, эта проблема разрешима за полиномиальное время.αα=α

Мне также кажется вероятным, что проблема в P, если - унарный язык.α

Итак, мои вопросы:

Для какой вышеупомянутая проблема решения PSPACE-завершена? Есть ли полная характеристика?α

Есть ли для которого проблема решения имеет некоторую промежуточную сложность (например, NP-complete)?α

mikero
источник
3
Какие операции разрешены в ваших регулярных выражениях? Ясно, что если у вас есть дополнение (или, скорее, симметричное различие), сложность задачи не зависит от . α
Эмиль Йержабек поддерживает Монику

Ответы:

17

Этот вопрос рассматривается в разделе 2 из [1], который показывает (теорема 2.6), что проблема

  • в P, если конечно;L(α)
  • coNP-complete, если бесконечна, но ограничена (т. е. для некоторых );L ( α ) w 1 w 2w k w 1 , , w kL(α)L(α)w1w2wkw1,,wk
  • PSPACE-завершить иначе.

[1] Гарри Б. Хант, Даниэль Дж. Розенкранц, Томас Г. Шимански, Об эквивалентности, содержании и проблемах покрытия для обычных и неконтекстных языков, Журнал компьютерных и системных наук, том 12, выпуск 2, 1976 г. , Страницы 222-268, ISSN 0022-0000, http://dx.doi.org/10.1016/S0022-0000(76)80038-4 . ( http://www.sciencedirect.com/science/article/pii/S0022000076800384 )

Дэвид
источник
3
Комментарий к предыдущему ответу (у меня недостаточно представителей на этом сайте, чтобы комментировать): Я не думаю, что это может быть правильно. Классическим результатом Мейера-Стокмейера (теорема 6.1 из [2]) является то, что универсальность для унарных регулярных языков является coNP-полной. [2] Л.Дж. Стокмейер и А.Р. Мейер. 1973. Слово проблемы, требующие экспоненциального времени (предварительный отчет). В материалах пятого ежегодного симпозиума ACM по теории вычислений (STOC '73). ACM, Нью-Йорк, Нью-Йорк, США, 1-9
Дэвид
2
Ваш комментарий меня смутил, так как «предыдущий ответ», на который вы ссылались, был удален. Но в любом случае унарные языки попадают в «ограниченный» случай вашего ответа с и . | w 1 | = 1k=1|w1|=1
Дэвид Эппштейн