Итак, я знаю, что проверка того, является ли обычный язык подмножеством обычного языка , разрешима, поскольку мы можем преобразовать их оба в DFA, вычислить , а затем проверить, является ли этот язык пустым.
Однако, поскольку это требует преобразования в DFA, возможно, что DFA и, следовательно, алгоритм тестирования будут экспоненциальными с точки зрения количества состояний во входных NFA.
Есть ли известный способ сделать это за полиномиальное время? Была ли эта проблема в целом доказана Co-NP завершена?
РЕДАКТИРОВАТЬ: это неверно, так как нет гарантии, что такое слово будет полиномиальным по числу штатов.
Ответы:
Проблема определения языковой локализации в NFAs является полной. Чтобы доказать это, легко уменьшить проблему универсальности для NFA (проверяя, есть ли ). Таким образом, вы должны определиться, но вы можете сделать это на лету.L ( A ) = Σ ∗PSPACE L(A)=Σ∗
Ваше наблюдение о co-NP неверно (но приятно). Такой свидетель действительно может быть проверен за полиномиальное время у свидетеля , но сам самый короткий свидетель может быть экспоненциальным по длине входных данных. Так как , то решение о несдерживании также является -complete.P S P A C EPSPACE=co−PSPACE PSPACE
Для того, чтобы государственные вещи более тщательно, решая ли является в размере (так как только должно быть дополнено) и в размере .P S P A C E B B N L O G S P A C E AL(A)⊆L(B) PSPACE B B NLOGSPACE A
источник
Вам следует взглянуть на статью Жан-Франсуа Раскина « Алгоритмы антицепи» для конечных автоматов .
В наших экспериментах тест включения на основе цепей выполнялся на один-два порядка лучше, чем «традиционные» подходы.
Если я правильно помню, этот алгоритм реализован в библиотеке libAMoRE ++ .
источник
Одна из лучших, наиболее совершенных и оптимизированных бесплатных бесплатных библиотек FSM, доступных в Интернете, - это библиотека AT & T FSM . Он реализует «fsmdifference» в точности так, как вы описываете, и для этого требуется определенный FSM без эпсилона. Одна идея состоит в том, чтобы свести к минимуму один или оба автомата, прежде чем делать разницу, что может помочь в некоторых случаях. (т.е. определение не то же самое, что минимизация.) Этот пакет также имеет «приблизительную» или «жадную» минимизацию, которая разработана, чтобы быть возможно более быстрой, чем полная минимизация.
Тем не менее, изучая подобные проблемы, я полагаю, что есть некоторое обобщение или построение автоматов, которые не встречаются в литературе, которые могут помочь с этой проблемой, избегая этапа детерминации, то есть, в основном, инвертируют NFA без создания дополнительного детерминированного FSM. Идея состоит в том, чтобы пересекать ребра NFA «параллельно» и отслеживать множество узлов, которые являются частью текущего «суперсостояния» (набора состояний), как со стандартным алгоритмом определения. Затем дополнение NFA принимает в том и только в том случае, если набор текущих суперсостоящих узлов «полностью неприемлем» (в отличие от определяющей конструкции, которая принимает iff «любое принятие»).
Тем не менее, я не видел это написано ранее и не вижу его через быстрый поиск в Интернете. Есть много ссылок, которые предполагают или подразумевают, что единственный способ работать с дополнением NFA - это определить его.
Вот две "близлежащие" ссылки, которые могут быть полезны для некоторых идей. Мне было бы интересно услышать о любых / других, которые "ближе". Вы упоминаете, что работаете над верификацией программы, которая может быть предметом более непосредственного исследования проблемы.
[1] Построение пересечения недетерминированных конечных автоматов с использованием Z-обозначения Назир Ахмад Зафар, Набиэль Сабир и Амир Али
[2] Конструкции комплементации для недетерминированных автоматов на бесконечных словах Орна Купферман и Моше Варди
источник