Wiem więc, że sprawdzenie, czy zwykły język jest podzbiorem zwykłego języka jest rozstrzygalne, ponieważ możemy przekonwertować je oba na DFA, obliczyć , a następnie sprawdzić, czy ten język jest pusty.S R ∩ ˉ S.
Ponieważ jednak wymaga to konwersji do DFA, możliwe jest, że DFA, a tym samym algorytm testowy, będą wykładnicze pod względem liczby stanów na wejściowych NFA.
Czy istnieje znany sposób na wykonanie tego w czasie wielomianowym? Czy ogólnie udowodniono, że problem Co-NP jest kompletny?
Należy zauważyć, że problem jest w Co-NP ponieważ słowo przyjęte przez , ale nie przez będzie wielomianem certifier że .
EDYCJA: jest to niepoprawne, ponieważ nie ma gwarancji, że takie słowo będzie wielomianowe w liczbie stanów.
Odpowiedzi:
Problemem decydującym o ograniczeniu języka w NFA jest . Aby to udowodnić, łatwo jest zredukować problem powszechności dla NFA (testowanie, czy ). W pewnym sensie musisz określić, ale możesz to zrobić w locie.L ( A ) = Σ ∗P.S.P.A C.mi L ( A ) = Σ∗
Twoja obserwacja na temat co-NP jest błędna (ale miła). Taki świadek rzeczywiście może być sprawdzany w czasie wielomianowym w świadku , ale sam najkrótszy świadek może być wykładniczy pod względem długości danych wejściowych. Ponieważ , podjęcie decyzji o niezawieraniu jest również .P S P A C EP.S.P.A C.mi= c o - PS.P.A C.mi P.S.P.A C.mi
Do rzeczy państwowych bardziej ostrożnie, decydując, czy jest w rozmiarze (ponieważ tylko należy uzupełnić) i w rozmiarze .L ( A ) ⊆ L ( B ) P.S.P.A C.mi b b N.L O G SP.A C.mi ZA
źródło
Powinieneś rzucić okiem na artykuł Jean-François Raskin Antygain Al Algorytmy dla automatów skończonych .
W naszych eksperymentach test inkluzyjny oparty na antychainach wykonał jeden lub dwa rzędy wielkości lepiej niż podejście „tradycyjne”.
Jeśli dobrze pamiętam, ten algorytm jest zaimplementowany w bibliotece libAMoRE ++ .
źródło
Jedną z najlepszych, najdokładniejszych i najbardziej zoptymalizowanych, bezpłatnych bibliotek FSM dostępnych online jest biblioteka AT&T FSM . Implementuje „fsmdifference” dokładnie tak, jak opisano, wymagając określonego FSM bez epsilon, aby zrobić różnicę. Jednym z pomysłów jest zminimalizowanie jednego lub obu systemów FSM przed wykonaniem różnicy, co może pomóc w niektórych przypadkach. (tzn. określanie nie jest tym samym, co minimalizowanie). Ten pakiet ma także „przybliżoną” lub „chciwą” minimalizację, która ma być możliwie szybsza niż pełna minimalizacja.
Jednak badając podobne problemy, uważam, że istnieje pewne uogólnienie lub konstrukcja FSM, które nie pojawiają się w literaturze, które mogą pomóc w rozwiązaniu tego problemu, unikając etapu determinacji, tj. Zasadniczo odwracając NFA bez tworzenia dodatkowego określonego FSM. Chodzi o to, aby przesuwać krawędzie NFA „równolegle” i śledzić zbiór węzłów, które są częścią bieżącego „superpaństwa” (zestawu stanów), podobnie jak w standardowym algorytmie determinującym. Następnie dopełnienie NFA akceptuje wtedy i tylko wtedy, gdy zbiór obecnych węzłów superpaństw „nie przyjmuje” (w przeciwieństwie do konstrukcji determinującej, która akceptuje „dowolną akceptację”).
Jednak nie widziałem tego wcześniej i nie widzę go za pomocą szybkiego wyszukiwania online. Istnieje wiele odniesień, które sugerują lub sugerują, że jedynym sposobem pracy z dopełnieniem NFA jest jego określenie.
Oto dwa „pobliskie” odniesienia, które mogą być przydatne w przypadku niektórych pomysłów. Chciałbym usłyszeć o / innych, którzy są „bliżsi”. Wspominasz, że pracujesz nad weryfikacją programu, która może być dziedziną, w której prowadzone są bardziej bezpośrednie badania problemu.
[1] Konstrukcja skrzyżowania niedeterministycznych automatów skończonych przy użyciu notacji Z Nazir Ahmad Zafar, Nabeel Sabir i Amir Ali
[2] Konstrukcje komplementacyjne dla niedeterministycznych automatów na nieskończonych słowach Orna Kupferman i Moshe Vardi
źródło