Minimalizowanie resztkowych automatów skończonych

Automaty szczątkowego stanu skończonego (RFSA, zdefiniowane w [DLT02]) to NFA, które mają kilka fajnych cech wspólnych z DFA. W szczególności zawsze istnieje kanoniczny minimalny rozmiar RFSA dla każdego zwykłego języka, a język rozpoznawany przez każdy stan w RFSA jest resztkowy, podobnie jak w DFA. Jednakże, podczas gdy minimalne stany DFA tworzą biject ze wszystkimi resztami, kanoniczne stany RFSA są biject z pierwotnymi resztami; może być ich wykładniczo mniej, więc RFSA mogą być znacznie bardziej kompaktowe niż DFA do reprezentowania zwykłych języków.

Nie wiem jednak, czy istnieje skuteczny algorytm minimalizujący RFSA, czy też wynik twardości. Jaka jest złożoność minimalizacji RFSA?

Z przeglądania [BBCF10] nie wynika, że ​​jest to powszechna wiedza. Z jednej strony spodziewam się, że będzie to trudne, ponieważ wiele prostych pytań dotyczących RFSA, takich jak „czy to NFA jest RFSA?” są bardzo trudne, w tym przypadku PSPACE. Z drugiej strony, [BHKL09] pokazuje, że kanoniczne RFSA można skutecznie nauczyć w minimalnie adekwatnym modelu nauczycielskim Angluin [A87], a skuteczne uczenie się minimalnego RFSA i minimalizowanie RFSA wydaje się, że powinno ono stanowić jednakową trudność. Jednak, o ile mogę powiedzieć, algorytm [BHKL09] nie implikuje algorytmu minimalizacji, ponieważ rozmiar kontrprzykładów nie jest ograniczony i nie jest jasne, jak skutecznie testować RFSA pod kątem równości w celu symulacji wyroczni z kontrprzykładów . Na przykład testowanie dwóch NFA pod kątem równości jest zakończone PSPACE .

Bibliografia

[A87] Angluin, D. (1987). Uczenie się regularnych zestawów z zapytań i kontrpróbek. Informacje i obliczenia, 75: 87-106

[BBCF10] Berstel, J., Boasson, L., Carton, O., i Fagnot, I. (2010). Minimalizacja automatów. arXiv: 1010.5318 .

[BHKL09] Bollig, B., Habermehl, P., Kern, C., i Leucker, M. (2009). Uczenie się NFA w stylu anglojęzycznym. W IJCAI , 9: 1004-1009.

[DLT02] Denis, F., Lemay, A., i Terlutte, A. (2002). Resztkowe automaty skończone. Fundemnta Informaticae , 51 (4): 339–368.

Niech problem „DFA NFA” oznacza, co następuje: Biorąc pod uwagę DFA A i liczbę całkowitą , czy istnieje NFA z co najwyżej stanami równoważnymi ? Podobnie, niech „DFA RFSA” oznacza problem uzyskany z powyższego, jeśli zastąpimy „NFA” „automatycznym stanem skończonym”.$\to$$A$k A $k$$k$$A$$\to$

Jiang i Ravikumar wykazali, że problem „DFA NFA” jest pełny dla PSPACE dzięki zmniejszeniu problemu „uniwersalności związku DFA”. Ten ostatni problem dał listę DFA i pyta, czy .1 , 2 , ... , n ⋃ n i = 1 L ( I ) = Ď $\to$$A_1,A_2,\ldots,A_n$$\bigcup_{i=1}^nL(A_i) = \Sigma^*$

Ich zmniejszenie przechodzi przez określenie języka z tych DFAS i odpowiednią całkowitą , tak, że przyjmowanie DFA L można skonstruować w czasie wielomian wielkości DFAS A ı . Następnie pokazują, że każdy NFA ( a tym bardziej każdy RFSA) akceptujący L potrzebuje co najmniej k stanów w przypadku, gdy i n i = 1 L ( A i ) jest uniwersalny i co najmniej k + 1 stwierdza inaczej. Następnie skonstruować k -state NFA N , która przyjmuje$L$$k$$L$$A_i$$L$$k$$\bigcup_{i=1}^nL(A_i)$$k+1$$k$$N$ iff ⋃ n i = 1 L ( A i ) = Σ ∗ .$L$$\bigcup_{i=1}^nL(A_i) = \Sigma^*$

Dowód ten został ponownie rozpatrzony później przez Gruber i Holzer (Developments in Language Theory '06). Używają tej samej redukcji, aby pokazać nieco inny wynik, który dotyczy złożoności obliczeniowej technik dolnej granicy dla NFA: (rozszerzony) zestaw do wygłupiania dla języka regularnego jest zbiorem S par słów ( x i , y i ) , takie, że dla każdego , że posiada x i y i ∈ L, ale wszystkim I ≠ J posiada: x ı y j ∉ r lub x $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$

$S$$k$$\bigcup_{i=1}^nL(A_i)$$x_i$$S$$N$$q_i$$x_i$$q$$x_i^{-1}L$$N$

$\to$$\to$$\to$$\to$

$N$

T. Jiang i B. Ravikumar. Minimalne problemy z NFA są trudne. SIAM Journal on Computing, 22 (6): 1117–1141, grudzień 1993.

Hermann Gruber i Markus Holzer. Znalezienie dolnych granic niedeterministycznej złożoności stanu jest trudne. W Oscar H. Ibarra i Zhe Dang, redaktorzy, 10. Międzynarodowa konferencja nt. Rozwoju teorii języka (DLT 2006), Santa Barbara (CA), USA, tom 4036 notatek z wykładów z informatyki, strony 363--374. Springer, czerwiec 2006 r.

Hermann Gruber i Markus Holzer. Znalezienie dolnych granic dla niedeterministycznej złożoności stanu jest trudne. Raport techniczny ECCC TR06-027, Electronic Colloquium on Computational Complexity, 2006.