вычисление минимального NFA для DFA

17

Много лет назад я слышал, что вычисление минимального NFA (недетерминированного конечного автомата) из DFA (детерминированного) было открытым вопросом, в отличие от обратного направления, которое было известно в течение десятилетий и хорошо исследовано с эффективным алгоритм. Кто-нибудь придумал алгоритм?О(NЛ.Г.N)

Быстрый поиск дал мне этот документ, который доказывает, что это определенно трудная проблема. По-видимому, алгоритм не приводится.

[1] Минимальные проблемы НФА трудны / Тао Цзян и Б. Равикумар

Мне напомнили об этой проблеме следующий вопрос на сайте CS.SE, для которого алгоритм минимизации DFA-> NFA будет тесно связан. Этот следующий вопрос кажется мне исследовательским уровнем. Я предложил перенести его в TCS и написал ответ, предлагающий статистическую / эмпирическую атаку.

[2] Какие условия для NFA для его эквивалентного DFA быть максимальным по размеру?

ВЗН
источник
4
В цитируемой вами статье показана PSPACE-полнота. В частности, проблема в PSPACE, которая сразу предлагает алгоритм. Какие алгоритмы вы ищете? Практические и / или эвристические? Самые известные оценки на показатель времени бега? Что-то другое?
Джошуа Грохов
8
На самом деле это не так уж необычно. До того, как стало известно, что проблема является PSPACE-полной, все попытки разработать эффективные алгоритмы потерпели неудачу, поэтому было опубликовано так мало. После того, как проблема стала известна как PSPACE-полная, никто не пытался разработать эффективные алгоритмы, потому что они знали, что потерпят неудачу, поэтому было опубликовано еще меньше.
Джеффс
4
(1) Что означает «обратное направление, известное десятилетиями и хорошо изученное с помощью эффективного алгоритма O (n lg n)»? Минимальный DFA для NFA с n состояниями может иметь экспоненциальный размер по n, поэтому он потребует некоторого нетривиального кодирования вывода. (2) Не существует такого понятия, как «минимальный NFA» для данного обычного языка. Сравните это с существованием минимального DFA.
Tsuyoshi Ito
1
JEFFE у вас есть хорошая точка зрения, но я уверен, что есть много полных задач Pspace, которые все еще имеют сложные алгоритмы, которые используют в своих интересах структуру проблемы, помимо простого перечисления всех возможных решений, верно? Признаться, я не могу думать ни о чем вне моей головы. может ты сможешь? думаю, это был бы еще один интересный вопрос, чтобы поставить здесь.
vzn
2
a+

Ответы:

25

Это действительно упрямая и хорошо изученная проблема. Что касается положительных результатов, точный алгоритм Kameda и Weiner, эвристический подход Polák и недавний подход с использованием SAT-решателей Geldenhuys et al. приходит на ум. Но, как представляется, гораздо более негативные результаты исключают другие возможные подходы (например, алгоритмы аппроксимации, особые случаи, менее мощные модели NFA, ...). Ниже приведены некоторые ссылки.

Т. Камеда и П. Вайнер. О минимизации состояния недетерминированных конечных автоматов. Операции IEEE на компьютерах, C-19 (7): 617–627, 1970.

А. Малчер. Минимизация конечных автоматов сложна в вычислительном отношении. Теоретическая информатика 327: 375-390, 2004.

Л. Полак. Минимализации NFA с использованием универсального автомата. Международный журнал основ информатики, 16 (5): 999–1010, 2005.

Г. Грамлич и Г. Шнитгер. Минимизация NFA и регулярных выражений. Симпозиум по теоретическим аспектам информатики (STACS 2005), LNCS 3404, с. 399–411.

Х. Грубер и М. Хольцер. Неподходимость недетерминированного состояния и сложность перехода в предположении P <> NP. Развитие теории языка (DLT 2007), LNCS 4588, с. 205–216.

Х. Грубер и М. Хольцер. Вычислительная сложность минимизации NFA для конечных и унарных языков. Теория языка и автоматов и приложения (LATA 2007), с. 261–272.

Х. Бьёрклунд и В. Мартенс. Граница управляемости для минимизации NFA. Международный коллоквиум по автоматам, языкам и программированию (ICALP 2008), LNCS 5126, с. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: Сокращение недетерминированных конечных автоматов с помощью SAT Solvers.Методы конечных состояний и обработка естественного языка (FSMNLP 2009), LNCS 6062, 81–92.

РЕДАКТИРОВАТЬ (8 июня 2015 г.)

Обновление: в следующей статье представлен эвристический алгоритм уменьшения размера недетерминированных автоматов Бючи, а также эксперименты на случайных автоматах. Как говорится в заключении, их метод применим и к NFA: «Хотя мы представили наши методы в контексте автоматов Büchi, большинство из них тривиально переносятся на более простой случай автоматов над конечными словами».

Ричард Майр, Лоренцо Клементе. Усовершенствованная минимизация автоматов. POPL 2013. Расширенный технический отчет EDI-INF-RR-1414.

Их инструмент командной строки Reduce v1.2 может быть вызван с опцией «-finite» для уменьшения данного NFA. Реализация с открытым исходным кодом и выпущена в соответствии с GNU General Public License.

Герман Грубер
источник
3
Знаете ли вы, есть ли реализации с открытым исходным кодом какой-либо из этих суеты вокруг?
jmite
Привет, Герман, большое спасибо за всю информацию! Я знаю, что с учетом NFA трудно найти наименьший эквивалент NFA. Но как насчет следующего: При наличии DFA найдите наименьший эквивалент NFA. Это сложно? Как сложно?
Майкл Вехар
Извините, теперь я вижу! Первый документ, указанный в списке, имеет следующий адрес: springerlink.com/content/y61724u571v487x5 Кроме того, другой документ, который вы перечислили, касается этого для конечных регулярных языков: hermann-gruber.com/data/lata07-final.pdf Спасибо за разъяснение этого для меня! :)
Майкл Вехар