Znalezienie najmniejszego DFA, który oddziela dwa słowa bez wyszukiwania z użyciem siły?

23

Biorąc pod uwagę dwa ciągi xiy, chcę zbudować DFA o minimalnym rozmiarze, który akceptuje x i odrzuca y. Jednym ze sposobów na to jest wyszukiwanie siłowe. Wymieniasz DFA zaczynając od najmniejszego. Próbujesz każdego DFA, aż znajdziesz taki, który akceptuje x i odrzuca y.

Chcę wiedzieć, czy istnieje inny znany sposób na znalezienie lub zbudowanie DFA o minimalnym rozmiarze, który akceptuje x i odrzuca y. Innymi słowy, czy możemy pokonać brutalne poszukiwanie siły?

Więcej szczegółów:

(1) Naprawdę chcę, aby algorytm znalazł minimalną wielkość DFA, a nie prawie minimalną wielkość DFA.

(2) Nie chcę tylko wiedzieć, jak duży lub mały jest minimalny DFA.

(3) Tutaj skupiam się tylko na przypadku, gdy masz dwa ciągi x i y.


Edytuj :

Dodatkowe informacje dla zainteresowanego czytelnika:

Załóżmy, i y są binarne łańcuchy o długości co najwyżej n . Wiadomo, że wynik jest DFA przyjmuje X i odrzuca Y z co najwyżej xynxy stanów. Zauważ, że istnieje okołonn DFA z alfabetem binarnym i co najwyżejnn stanów. Dlatego podejście z użyciem brutalnej siły nie wymagałoby od nas liczenia więcej niżnn DFA. Wynika z tego, że podejście brutalnej siły nie mogło zająć więcej niżnnn raz.nn

Pomocne dla mnie slajdy: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf

Michael Wehar
źródło
2
@ AndrásSalamon Czy nadal jest NP-kompletny, jeśli każdy zestaw do rozróżnienia składa się tylko z jednego ciągu? Wydaje mi się, że powinno to być rozsądne.
mhum
6
@ mhum problem polegający na tym, że istnieje wiele różnych zwykłych języków, które oddzielają dwa ciągi - minimalizacja DFA znajdzie najlepszy automat dla jednego z tych języków, ale nie zrobi nic, aby porównać go z automatami dla innych języków oddzielających.
David Eppstein,
4
Jeśli i y mają różne długości, przy czym większa od długości n , to łatwo szybko znaleźć DFA z O ( log n ) stwierdza, że oddziela je: po prostu użyć cykl o długości p , gdzie p nie dzieli | x | - | y | . Znajdź p , próbując 2 , 3 , 5 , w kolejności, aż znajdziesz odpowiednią str . Jeśli x i y są tej samej długości, to wyxynO(logn)pp|x||y|p2,3,5,pxykonstrukcja Robsona, w artykule z 1996 roku, daje prostą maszynę, którą można znaleźć, szukając rozmiaruO(n). Żadna z konstrukcji nie jest gwarantowana jako najmniejszy DFA. O(n)O(n)
Jeffrey Shallit,
3
Notatki Shallita, połączone powyżej, zawierają użyteczną obserwację, że najgorszym przypadkiem problemu separacji jest to, że alfabet jest binarny: zawsze można podzielić większe alfabety na dwa podzbiory, które wciąż rozróżniają dwa słowa wejściowe i szukają automatu binarnego, który traktuje litery w jednym podzbiorze jako 0 i litery w drugim podzbiorze jako 1. Ale szukanie minimalnego automatu oddzielającego nie wydaje się pomocne, ponieważ możesz być w stanie wykorzystać dodatkowe informacje z oryginalnego alfabetu, aby uzyskać lepsze wyniki niż w przypadku odwzorowania na alfabet binarny.
David Eppstein
3
szczególny przypadek tego ostatniego pytania, w którym rozmiary w zestawie i w zestawie są równe 1. minimalnym automatom skończonym podanym w słowach i słowach . w tej odpowiedzi wymieniono część literatury naukowej, w tym heurystykę.
vzn

Odpowiedzi:

9

Gdybym musiał to zrobić w praktyce, użyłbym solvera SAT.

Pytanie, czy istnieje DFA ze stanami , które akceptuje x i odrzuca y, można łatwo wyrazić jako instancję SAT. Na przykład jednym ze sposobów jest posiadanie 2 k 2 zmiennych logicznych: z s , b , t jest prawdą, jeśli DFA przechodzi ze stanu s do stanu t na bicie wejściowym b . Następnie dodaj kilka klauzul, aby wymusić, że jest to DFA, oraz niektóre zmienne i klauzule, aby wymusić, że akceptuje x i odrzuca y .kxy2k2zs,b,tstbxy

Teraz użyj wyszukiwania binarnego na aby znaleźć najmniejsze k takie, że istnieje DFA tego rodzaju. Na podstawie tego, co przeczytałem w artykułach na temat pokrewnego problemu, spodziewałbym się, że może to być dość skuteczne w praktyce.kk


Możliwe są inne kodowania tego jako SAT. Na przykład możemy użyć kodowania śledzenia:

  • Jeśli ma długość m , można dodać m lg k zmiennych logicznych: let s 0 , y 1 , ... , s m być sekwencja stanów które przechodzi na wejściowym x , i reprezentują każdy s i przy użyciu lg k zmiennych logicznych.xmmlgks0,s1,,smxsilgk

  • Teraz dla każdego takiego, że x i = x j , masz ograniczenie, którei,jxi=xj .si1=sj1si=sj

  • Następnie rozszerz to, aby obsłużyć : niech t 0 , , t n będzie sekwencją stanów przemierzonych na wejściu y , i reprezentuje każde t j przy użyciu zmiennych logicznych lg k . Dla każdego i , j tak, że y i = y j , dodaj ograniczenie, że t i - 1 = t j - 1yt0,,tnytjlgki,jyi=yj .ti1=tj1ti=tj

  • Podobnie, dla każdego takiego, że x i = y j , dodaj ograniczenie, które s i - 1 = t j - 1i,jxi=yj .si1=tj1si=tj

  • Oba ślady muszą zaczynać się od tego samego punktu początkowego, więc dodaj warunek, że (WLOG możesz wymagać s 0 = t 0 = 0 ).s0=t0s0=t0=0

  • Aby upewnić się, że DFA używa tylko stanów , należy wymagać, aby 0 s i < k oraz 0 t j <k0si<k dla wszystkich i , j .0tj<ki,j

  • Na koniec, aby zakodować wymaganie, że jest akceptowane, a y odrzucane, wymagaj, aby sxy .smtn

Wszystkie te wymagania można zakodować jako klauzule SAT.

Tak jak poprzednio, użyjesz wyszukiwania binarnego na aby znaleźć najmniejsze k, dla którego istnieje taki DFA.kk

DW
źródło
3
zauważ, że faktycznie będzie to lepsze od poszukiwania siły, jeśli występują pewne symetrie w problemie i są one rozpoznawane przez solver, ale obecnie może być trudne do zidentyfikowania / wyizolowania (dla człowieka lub maszyny). istnieje również nowsza / powiązana „technologia” teorii modulo satysfakcji i programowania zestawu odpowiedzi, z których niektóre mają „wbudowane” predykaty wykresów lub mogą wspierać ich definicje.
vzn