Хорошо известно, что следующая проблема является PSPACE-полной:
Учитывая регулярное выражение , ?L ( β ) = Σ ∗
Как насчет определения эквивалентности другим (фиксированным) регулярным выражениям ?
Учитывая регулярное выражение , ?L ( β ) = L ( α )
Известно следующее:
Для проблема является PSPACE-полной
Для или, в более общем случае, который описывает конечное множество, эта проблема разрешима за полиномиальное время.α
Мне также кажется вероятным, что проблема в P, если - унарный язык.
Итак, мои вопросы:
Для какой вышеупомянутая проблема решения PSPACE-завершена? Есть ли полная характеристика?
Есть ли для которого проблема решения имеет некоторую промежуточную сложность (например, NP-complete)?
Ответы:
Этот вопрос рассматривается в разделе 2 из [1], который показывает (теорема 2.6), что проблема
[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 )
источник