obliczanie minimalnego NFA dla DFA

17

Wiele lat temu słyszałem, że obliczenie minimalnego NFA (niedeterministycznego automatu skończonego) z DFA (deterministycznego) było otwartym pytaniem, w przeciwieństwie do odwrotnego kierunku, który jest znany od dziesięcioleci i jest dobrze zbadany z wydajnym algorytm. Czy ktoś wymyślił algorytm?O(nlg⁡n)

Szybkie wyszukiwanie dało mi ten artykuł, który dowodzi, że jest to zdecydowanie trudny problem. Najwyraźniej nie podano żadnego algorytmu.

[1] Minimalne problemy z NFA są trudne / Tao Jiang i B. Ravikumar

Przypomniałem sobie o tym problemie następujące pytanie na stronie CS.SE, z którym algorytm minimalizacji DFA-> NFA byłby ściśle powiązany. To pytanie wydaje mi się na poziomie badawczym. Zasugerowałem migrację do TCS i napisałem odpowiedź sugerującą atak statystyczny / empiryczny.

[2] Jakie są warunki maksymalnego rozmiaru NFA dla jego równoważnego DFA?

ds.algorithms reference-request fl.formal-languages automata-theory optimization vzn
źródło
4
Artykuł, który cytujesz, pokazuje kompletność PSPACE. W szczególności problem dotyczy PSPACE, co natychmiast sugeruje algorytm. Jakiego rodzaju algorytmów szukasz? Praktyczne i / lub heurystyczne? Najbardziej znane granice wykładnika czasu działania? Coś innego?
Joshua Grochow
8
Właściwie to wcale nie jest takie niezwykłe. Zanim wiadomo było, że problem został ukończony w PSPACE, wszystkie próby opracowania wydajnych algorytmów zakończyły się niepowodzeniem, więc opublikowano niewiele. Po tym, jak wiadomo, że problem jest kompletny z PSPACE, nikt nie próbował opracować wydajnych algorytmów, ponieważ wiedzieli, że zawiodą, więc opublikowano jeszcze mniej.
Jeffε
4
(1) Co oznacza „odwrotnie kierunek znany od dziesięcioleci i dobrze zbadany za pomocą wydajnego algorytmu O (n lg n)”? Minimalny DFA dla NFA ze stanami n może mieć wykładniczy rozmiar w n, więc wymagałoby to trochę nietypowego kodowania wyjściowego. (2) Nie ma czegoś takiego jak „minimalny” NFA dla danego języka regularnego. Porównaj to z istnieniem minimalnego DFA.
Tsuyoshi Ito
1
JEFFE, masz rację, ale jestem pewien, że istnieje wiele problemów z kompletnym obszarem Pspace, które wciąż mają wyrafinowane algorytmy, które wykorzystują strukturę problemu oprócz wyliczenia wszystkich możliwych rozwiązań, prawda? przyznaję, że nie mogę wymyślić niczego poza moją głową. może potrafisz? myślę, że byłoby to kolejne interesujące pytanie do postawienia tutaj.
dniu
2
a+

Odpowiedzi:

25

To naprawdę uparty - i dobrze przestudiowany - problem. Jeśli chodzi o pozytywne wyniki, dokładny algorytm Kamedy i Weinera, heurystyczne podejście Poláka oraz ostatnie podejście wykorzystujące solwery SAT Geldenhuys i in. przychodzą do głowy. Wydaje się jednak, że istnieją znacznie bardziej negatywne wyniki wykluczające inne możliwe podejścia (np. Algorytmy aproksymacyjne, przypadki szczególne, słabsze modele NFA, ...) Patrz poniżej niektóre źródła.

T. Kameda i P. Weiner. O minimalizacji stanu niedeterministycznych automatów skończonych. Transakcje IEEE na komputerach, C-19 (7): 617–627, 1970.

A. Malcher. Minimalizowanie automatów skończonych jest trudne obliczeniowo. Theoretical Computer Science 327: 375-390, 2004.

L. Polák. Minimalizacje NFA przy użyciu automatu uniwersalnego. International Journal of Foundations of Computer Science, 16 (5): 999–1010, 2005.

G. Gramlich i G. Schnitger. Minimalizowanie NFA i wyrażeń regularnych. Sympozjum na temat teoretycznych aspektów informatyki (STACS 2005), LNCS 3404, s. 399–411.

H. Gruber i M. Holzer. Niedopuszczalność niedeterministycznego stanu i złożoności przejścia przy założeniu P <> NP. Rozwój teorii języka (DLT 2007), LNCS 4588, s. 205–216.

H. Gruber i M. Holzer. Złożoność obliczeniowa minimalizacji NFA dla języków skończonych i jednoargumentowych. Teoria języków i automatów oraz aplikacje (LATA 2007), s. 261–272.

H. Björklund i W. Martens. Granica podatności na minimalizację NFA. Międzynarodowe kolokwium na temat automatów, języków i programowania (ICALP 2008), LNCS 5126, s. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: Redukowanie niedeterministycznych automatów skończonych za pomocą SAT Solvers. Metody stanów skończonych i przetwarzanie języka naturalnego (FSMNLP 2009), LNCS 6062, 81–92.

EDYCJA (8 czerwca 2015 r.)

Aktualizacja: Poniższy artykuł przedstawia heurystyczny algorytm zmniejszania wielkości niedeterministycznych automatów Büchi wraz z eksperymentami na automatach losowych. Jak stwierdzili we wniosku, ich metoda ma również zastosowanie do NFA: „Podczas gdy przedstawiliśmy nasze metody w kontekście automatów Büchi, większość z nich w sposób trywialny odnosi się do prostszego przypadku automatów zamiast skończonych słów”.

Richard Mayr, Lorenzo Clemente. Zaawansowana minimalizacja automatów. POPL 2013. Rozszerzony raport techniczny EDI-INF-RR-1414.

Narzędzie wiersza polecenia Reduce v1.2 można wywołać z opcją „-finite” w celu zmniejszenia danego NFA. Implementacja jest open source i wydana na licencji GNU General Public License.

Hermann Gruber
źródło
3
Czy wiesz, czy są jakieś implementacje open-source któregoś z nich?
jmite
Cześć Hermann, bardzo dziękuję za wszystkie informacje! Wiem, że biorąc pod uwagę NFA, trudno jest znaleźć najmniejszy odpowiednik NFA. Ale co z następującymi: Biorąc pod uwagę DFA, znajdź najmniejszy odpowiednik NFA. Czy to jest trudne? Jak ciężko?
Michael Wehar,
Przepraszam, widzę teraz! Pierwszy wymieniony artykuł dotyczy tego: springerlink.com/content/y61724u571v487x5 Również inny wymieniony artykuł dotyczy tego w skończonych językach regularnych: hermann-gruber.com/data/lata07-final.pdf Dziękujemy za wyjaśnienie mi tego! :)
Michael Wehar,