Минимизация остаточных конечных автоматов

Остаточные автоматы в конечном состоянии (RFSA, определенные в [DLT02]) - это NFA, которые имеют некоторые общие черты с DFA. В частности, для каждого обычного языка всегда существует канонический RFSA минимального размера, а язык, распознаваемый каждым государством в RFSA, является остаточным, как и в DFA. Однако, хотя минимальные состояния DFA формируют биекцию со всеми невязками, канонические состояния RFSA находятся в биекции с простыми невязками; их может быть экспоненциально меньше, поэтому RFSA могут быть гораздо более компактными, чем DFA, для представления обычных языков.

Тем не менее, я не могу сказать, есть ли эффективный алгоритм для минимизации RFSA или есть ли результат жесткости. Какова сложность минимизации RFSA?

Из просмотра [BBCF10] не кажется, что это общеизвестно. С одной стороны, я ожидаю, что это будет трудно, потому что много простых вопросов о RFSA, таких как «это NFA, RFSA?» очень трудно, PSPACE-завершено в этом случае. С другой стороны, [BHKL09] показывает, что канонические RFSA эффективно усваиваются в минимально адекватной модели учителя Англуина [A87], и эффективное изучение минимального RFSA и минимизация RFSA кажется таким же трудным. Однако, насколько я могу судить, алгоритм [BHKL09] не подразумевает алгоритм минимизации, поскольку размер контрпримеров не ограничен, и неясно, как эффективно тестировать RFSA на равенство для симуляции оракула контрпримеров. , Например, проверка двух NFA на равенство завершена PSPACE .

Ссылки

[A87] Angluin, D. (1987). Изучение регулярных наборов из запросов и контрпримеров. Информация и вычисления, 75: 87-106

[BBCF10] Берстель Дж., Боассон Л., Картон О. и Фагнот И. (2010). Минимизация автоматов. arXiv: 1010.5318 .

[BHKL09] Bollig B., Habermehl P., Kern C. & Leucker M. (2009). Изучение английского стиля NFA. В IJCAI , 9: 1004-1009.

[DLT02] Денис Ф., Лемей А. и Терлютт А. (2002). Остаточные автоматы конечного состояния. Fundemnta Informaticae , 51 (4): 339-368.

Пусть задача «DFA NFA» обозначает следующее: При наличии DFA и целого числа существует ли NFA с не более чем состояниями, эквивалентными ? Аналогично, пусть «DFA RFSA» обозначает проблему, полученную из вышеизложенного, если мы заменим «NFA» на «остаточный автомат конечного состояния».A k k A $\to$$A$$k$$k$$A$$\to$

Цзян и Равикумар показали, что проблема «DFA NFA» полна PSPACE путем сокращения проблемы «универсальности профсоюзов DFA». Последняя проблема дала список DFA и спрашивает, если .A 1$\to$⋃ n i = 1 L ( A i ) = Σ $A_1,A_2,\ldots,A_n$$\bigcup_{i=1}^nL(A_i) = \Sigma^*$

Их сокращение происходит путем определения языка из этих DFA и подходящего целого числа , так что DFA, принимающий может быть построен за полином по времени в размере DFA . Затем они показывают, что каждому NFA (т.е. тем более каждому RFSA), принимающему необходимо по крайней мере состояний в случае, если является универсальным и по крайней мере состояний в противном случае. Затем они построить -state НКА , который принимает тогда и только тогда .k L A i L k ⋃ n i = 1 L ( A i ) k + $L$$k$$L$$A_i$$L$$k$$\bigcup_{i=1}^nL(A_i)$$k+1$$k$$N$$L$$\bigcup_{i=1}^nL(A_i) = \Sigma^*$

Это доказательство было позже пересмотрено Грубером и Хольцером («Развитие в теории языка», 2006 г.). Они используют одно и то же сокращение, чтобы показать немного другой результат, который касается вычислительной сложности методов нижней границы для NFA: (расширенный) набор дурака для обычного языка - это набор пар слов , такой, что для каждого держит , но и для всех справедливо: или .S ( x i , y i ) i $R$$S$$(x_i,y_i)$$i$$x_iy_i\in L$$i\neq j$$x_iy_j \notin R$$x_jy_i\notin R$

Для приведенного выше сокращения они показывают, что существует расширенный набор дурака размера в случае, если универсален. Изучая доказательства Грубера и Хольцера, легко заметить, что каждое «левое слово» в множестве таково, что упомянутый выше NFA может перейти из начального состояния в только одно состояние при чтении . То есть язык, принятый из состояния равен , и, следовательно, является остаточным автоматом конечных состояний.k ⋃ n i = 1 L ( A i ) x i$S$$k$$\bigcup_{i=1}^nL(A_i)$$x_i$$S$q i x i q x - 1 i L $N$$q_i$$x_i$$q$$x_i^{-1}L$$N$

Если приведенные выше рассуждения не содержат ошибок, это приводит сведению проблемы универсальности объединений DFA к проблеме «DFA RFSA», и, таким образом, она сложна для PSPACE. Членство в PSPACE следует тому же принципу, что и проблемы DFA NFA, поэтому проблема «DFA RFSA» является PSPACE-полной. Будучи более общим, но все же в PSPACE, проблема «NFA RFSA» также является PSPACE-полной.→ → $\to$$\to$$\to$$\to$

Для тех, кто хочет восстановить приведенный выше аргумент (пожалуйста, не принимайте это как должное, моя статья была немного поспешной), я рекомендую прочитать доказательство теоремы 15 в отчете ECCC, цитируемом ниже. В частности, на рисунке 5 на странице 18 изображен автомат который, как я утверждаю, является RFSA.$N$

Т. Цзян и Б. Равикумар. Минимальные проблемы NFA трудны. Журнал SIAM по вычислительной технике, 22 (6): 1117–1141, декабрь 1993 г.

Герман Грубер и Маркус Хольцер. Трудно найти нижние границы для недетерминированной сложности состояний. В книге «Оскар Х. Ибарра и Же Данг», редакторы 10-й Международной конференции по развитию теории языка (DLT 2006), Санта-Барбара (Калифорния), США, том 4036 «Конспект лекций в области компьютерных наук», страницы 363–374. Springer, июнь 2006 г.

Герман Грубер и Маркус Хольцер. Трудно найти нижние границы для недетерминированной сложности состояний. Технический отчет ECCC TR06-027, Электронный коллоквиум по вычислительной сложности, 2006.