Czy istnieje skuteczny test, jeśli NFA akceptuje podzbiór innego NFA?

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. $R$ $S$ $R \cap \bar{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 . $R$ $S$ $R \not \subseteq S$

EDYCJA: jest to niepoprawne, ponieważ nie ma gwarancji, że takie słowo będzie wielomianowe w liczbie stanów.

— jmite
źródło

czy to pytanie teoretyczne, czy w praktyce? czasami w przypadku konkretnego „rozkładu” danych wejściowych napotkanych w praktyce problem pełnego Pspace może być „uruchomiony” w czasie P.

— vzn

Idealnie jest to teoretyczne, ale dowody, nad którymi pracuję, są w dużej mierze oparte na testach komputerowych, co oznacza, że szybki algorytm byłby zdecydowanie przydatny.

— jmite

więc tak, istnieje całkiem prosty algorytm, który działa po prostu równolegle śledząc przejścia dla każdej z dwóch maszyn i śledząc wynikowe zestawy stanów, podobnie jak algorytm wyznaczania standardowego. nie wiem, czy jest to gdzieś w literaturze, jest tak proste, że tak jest. czy już używasz jakiegoś algorytmu? byłoby pomocne, gdybyś to zacytował. pomocne byłyby również dodatkowe informacje na temat rodzaju danych wejściowych. brzmi to tak, jakbyś chciał ustalić, czy skrzyżowanie dwóch NFA jest puste? chcesz język skrzyżowania, czy tylko T / N, jeśli nie jest pusty?

— vzn

Po prostu szukam bo jeśli ona pusta, pomysł jest Szukam jeśli aby sprawdzić, czy . Algorytm przejścia równoległego działa, myślę, że najtrudniejsze jest przyjęcie komplementu z NFA, musisz najpierw przekonwertować na DFA. Algorytm, którego teraz używam, jest po prostu brutalną siłą, ponieważ mam do czynienia tylko z językami skończonymi.

R - S = {}

$R-S=\{\}$

R \subseteq S

$R \subseteq S$

— jmite

sądzę, że może istnieć sposób na przejście przez dwa NFA bez konwersji na DFA 1., nawet znalezienie uzupełnienia jednego. ale nie widziałem tego w ref.

— vzn

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. $PSPACE$ $L(A)=\Sigma^*$

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ż . $PSPACE=co-PSPACE$ $PSPACE$

Do rzeczy państwowych bardziej ostrożnie, decydując, czy jest w rozmiarze (ponieważ tylko należy uzupełnić) i w rozmiarze . $L(A)\subseteq L(B)$ $PSPACE$ $B$ $B$ $NLOGSPACE$ $A$

— Shaull
źródło

Masz całkowitą rację. Miałem do czynienia z konkretną klasą NFA, w której to, co powiedziałem, ma moc, ale z pewnością może nie być z ogólnymi nieskończonymi NFA. Dzięki!

— jmite

Nie miałbyś odniesienia do gazety lub podręcznika, który potwierdza, że jest to kompletny PSPACE, prawda?

— jmite

To nie jest bardzo szczegółowy dowód, ale myślę, że to zrobi: wisdom.weizmann.ac.il/~vardi/av/notes/lec4.ps

— Shaull

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 ++ .

— Dan
ź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

— vzn
źródło