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

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 są binarne łańcuchy o długości co najwyżej . Wiadomo, że wynik jest DFA przyjmuje i odrzuca z co najwyżej $x$ $y$ $n$ $x$ $y$ stanów. Zauważ, że istnieje około $\sqrt{n}$ DFA z alfabetem binarnym i co najwyżej $n^{\sqrt{n}}$ stanów. Dlatego podejście z użyciem brutalnej siły nie wymagałoby od nas liczenia więcej niż $\sqrt{n}$ DFA. Wynika z tego, że podejście brutalnej siły nie mogło zająć więcej niż $n^{\sqrt{n}}$ raz. $n^{\sqrt{n}}$

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

automata-theory dfa fsm Michael Wehar
źródło

@ 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

@ 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,

Jeśli

mają różne długości, przy czym większa od długości

, to łatwo szybko znaleźć DFA z

stwierdza, że oddziela je: po prostu użyć cykl o długości

, gdzie

nie dzieli

. Znajdź

, próbując

w kolejności, aż znajdziesz odpowiednią

. Jeśli

są tej samej długości, to

x

$x$

y

$y$

n

$n$

O (\log n)

$O(\log n)$

p

$p$

p

$p$

| x | - | y |

$|x|-|y|$

p

$p$

2, 3, 5, \dots

$2, 3, 5,\ldots$

p

$p$

x

$x$

y

$y$

konstrukcja Robsona, w artykule z 1996 roku, daje prostą maszynę, którą można znaleźć, szukając rozmiaru

. Żadna z konstrukcji nie jest gwarantowana jako najmniejszy DFA.

O (\sqrt{n})

$O(\sqrt{n})$

O (n)

$O(n)$

Jeffrey Shallit,

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

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:

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

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

Teraz użyj wyszukiwania binarnego na aby znaleźć najmniejsze 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. $k$ $k$

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

Jeśli ma długość , można dodać zmiennych logicznych: let być sekwencja stanów które przechodzi na wejściowym , i reprezentują każdy przy użyciu zmiennych logicznych. $x$ $m$ $m\lg k$ $s_0,s_1,\dots,s_m$ $x$ $s_i$ $\lceil \lg k \rceil$
Teraz dla każdego takiego, że , masz ograniczenie, które $i,j$ $x_i=x_j$ . $s_{i-1}=s_{j-1} \implies s_i=s_j$
Następnie rozszerz to, aby obsłużyć : niech będzie sekwencją stanów przemierzonych na wejściu , i reprezentuje każde przy użyciu zmiennych logicznych . Dla każdego tak, że , dodaj ograniczenie, że $y$ $t_0,\dots,t_n$ $y$ $t_j$ $\lg k$ $i,j$ $y_i=y_j$ . $t_{i-1}=t_{j-1} \implies t_i=t_j$
Podobnie, dla każdego takiego, że , dodaj ograniczenie, które $i,j$ $x_i=y_j$ . $s_{i-1}=t_{j-1} \implies s_i=t_j$
Oba ślady muszą zaczynać się od tego samego punktu początkowego, więc dodaj warunek, że (WLOG możesz wymagać ). $s_0=t_0$ $s_0=t_0=0$
Aby upewnić się, że DFA używa tylko stanów , należy wymagać, aby oraz $k$ $0 \le s_i < k$ dla wszystkich . $0 \le t_j <k$ $i,j$
Na koniec, aby zakodować wymaganie, że jest akceptowane, a odrzucane, wymagaj, aby $x$ $y$ . $s_m \ne t_n$

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

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

DW
źródło

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