Ile DFA akceptuje dwa podane ciągi?

28

Napraw liczbę całkowitą i alfabet Σ = { 0 , 1 } . Zdefiniuj D F A ( n ) jako zbiór wszystkich automatów skończonych w stanach n ze stanem początkowym 1. Rozważamy wszystkie DFA (nie tylko połączone, minimalne lub nie-zdegenerowane); w ten sposób | D F A ( n ) | = n 2 n 2 n .nΣ={0,1}DFA(n)n|DFA(n)|=n2n2n

Teraz rozważmy dwa łańcuchy i zdefiniujemy K ( x , y ) jako liczbę elementów D F A ( n ), które akceptują zarówno x, jak i y .x,yΣK(x,y)DFA(n) xy

Pytanie: Jaka jest złożoność obliczania ?K(x,y)

To pytanie ma wpływ na uczenie maszynowe .

Edycja: Teraz, gdy jest nagroda za to pytanie, przypuszczam, że nieco większa precyzja w sformułowaniu jest w porządku. Dla , niech D F A ( n ) będzie zbiorem n 2 n 2 n automatów, jak zdefiniowano powyżej. Dla x , y { 0 , 1 } zdefiniuj K n ( x , y ) jako liczbę automatów w D F A ( n ), które akceptują oban1DFA(n)n2n2nx,y{0,1}Kn(x,y)DFA(n) i y . Pytanie: czy K n ( x , y ) można obliczyć w czasie p o l y ( n , | x | , | y | ) ?xyKn(x,y)poly(n,|x|,|y|)

Aryeh
źródło
2
Jeśli naprawisz DFA bez ustalania stanów końcowych, to albo odwzorowuje xiy na ten sam stan, w którym to przypadku jedynym ograniczeniem jest to, że stan musi być końcowy, lub odwzorowuje je na dwa różne stany, w którym to przypadku jedynym ograniczeniem jest to, że oba muszą być ostateczne. W związku z tym przeredagowałbym twój problem na „ile DFA mapuje xy do różnych stanów?”.
a3nm
3
Aryeh, czy możesz wyjaśnić liczbę ? Nie mogę uzyskać współczynnika 2 n . Dodano: Ups, zapomniałem podać końcowe stany. W każdym razie, dla dobra innych, oto jak liczyć. Dla każdego stanu określ, gdzie iść na wejściach 0 i 1 ; co odpowiada n 2 n . Określ zestaw stanów końcowych; to 2 n . n2n2n2n01n2n2n
Srivatsan Narayanan
2
Rzeczywiście, nie obchodzi mnie, co stanie się z ciągami innymi niż i y . Myślę, że potrzeba pewnej ilości punktów, aby rozpocząć nagrodę? xy
Aryeh
4
Najmniejszy automat, który akceptuje i y, ma jeden stan, więc nie sądzę, aby był on bardzo pouczający ...xy
Aryeh
3
Oto pomysł: musimy tylko znać liczbę -state DFAS które kończą się w tym samym stanie na x i y . Niech liczba ta jest m i M jest całkowitą ilość DFAS, czyli M = n 2 n 2 n . Zatem odpowiedź brzmi 1nxymMM=n2n2n12m+14(Mm)mxyx=0ab=1bl0 a 1 b mmax{a,b}0a1bm

Odpowiedzi:

1

Pytanie jest więc dość krótkie, ale bardzo interesujące. Przypuszczam, że wejście jest w jednoskładnikowa, a i w trybie binarnym (lub mamy problemy, jak wskazał odpowiedź Kai).x ynxy

Przede wszystkim, jeśli chcesz poznać przybliżoną wartość , możesz po prostu wygenerować kilka losowych DFA, a to da ci dobre przybliżenie. (Zastanawiam się, czy ta klasa złożoności ma nazwę).K(x,y)

Zatem znajomość wydaje się trudnym problemem. Jak wskazano w komentarzach a3_nm i Kaveh, pytanie jest odpowiednikiem określenia liczby automatów, dla których i iść do tego samego stanu. Oznaczę prawdopodobieństwo, że przejdą do tego samego stanu przez .x y pK(x,y)xyp

Aktualizacja: Niektóre rzeczy, które tu napisałem, nie były prawdziwe, teraz je naprawiłem.

Łatwo zauważyć, że . Mamy równość, jeśli to wszystkie zera, a to zero, z wyjątkiem ostatniego bitu, który jest 1. Czy istnieją inne przypadki? Nie wiem Jeśli na przykład jest pustym łańcuchem, , to .x y x y = 00 p = n + 1p1/nxyxy=00p=n+1(n1)n

Aby uprościć problem, zacząłem nawet myśleć o tym, co się dzieje, jeśli i są jednoskładnikowa. Jeśli oba są co najmniej a ich różnica jest podzielna przez, a następnie . Czy istnieje prosta formuła dla wersji jednoargumentowej?y n n ! p = 1xynn!p=1

domotorp
źródło
Wyjaśniłem problem - pożądany jest algorytm (lub redukcja znanego trudnego problemu). Przybliżenie próbkowania jest zastosowane w artykule, w którym wprowadzono to jądro: portal.acm.org/citation.cfm?id=1577108poly(n,|x|,|y|)
Aryeh
2
Co do wersji jednoargumentowej: istnieje tylko wielomianowo wiele jednoargumentowych automatów stanowych, więc założę się, że istnieje algorytm do obliczania w tym przypadku. K n ( x , y )nKn(x,y)
Aryeh
Rzeczywiście, masz całkowitą rację, że wersja jednoargumentowa jest obliczalna. Nadal zastanawiam się, jak prosta jest formuła dla danego xiy.
domotorp
Zastosowana przez ciebie redukcja jest błędna: xiy mogą być akceptowane przez te same automaty i kończyć się w zupełnie innych stanach, w rzeczywistości mogą dzielić tylko stan początkowy na swoich ścieżkach, co jest prawdą dla wszystkich łańcuchów.
amn.
@amnn: Minęły trzy lata, odkąd to napisałem, ale czy trzeci akapit mojej odpowiedzi nie wyjaśnia, dlaczego mam do czynienia tylko z tym samym stanem?
domotorp
0

Mogę bardzo nie rozumieć tego, ale stwierdziłeś, że jest naprawiony, więc wszystkie DFA o tym rozmiarze można uznać za wstępnie obliczone i przechowywane w łatwo symulowalnym formacie. Oblicz w następujący sposób:K.nK

Na wejściu , gdziey x , y Σ xyx,yΣ

  1. Przechowywać iyxy
  2. zainicjuj licznik na0c0
  3. dla każdego z Twoich DFAn2n2n
  4. za. symuluj to dla obu słów (ten krok to )O(|xy|)

    b. przyrost jeśli oba przebiegi symulacji są akceptowanec

  5. wyjściec

W sumie obliczenia mają złożoność liniową. Odpowiedź jest zupełnie inna dla .K(n,x,y)

Kai
źródło
3
Wyraźnie wypróbowanie wszystkich maszyn będzie działać. Aryeh chce wiedzieć, czy może istnieje algorytm wielomianowy lub inny wynik twardości.
Lew Reyzin
Ściśle mówiąc, jest to czas wielomianowy na wejściu, jeśli n nie jest częścią wejścia, to właśnie mówił Kai. Ale pytanie jest wyraźnie inne.
domotorp
4
Rozumiem. Nie sądzę, żeby to miał na myśli, mówiąc „naprawić ”. Myślę, że naturalna interpretacja problemu nie polega na trywializacji. n
Lev Reyzin
1
Tak, dzięki za wskazanie luki, Kai. Zostało to naprawione :)
Aryeh