Ile DFA akceptuje dwa podane ciągi?

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

Teraz rozważmy dwa łańcuchy i zdefiniujemy jako liczbę elementów które akceptują zarówno jak i . $x,y\in\Sigma^*$ $K(x,y)$ $DFA(n)$ $x$ $y$

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 będzie zbiorem automatów, jak zdefiniowano powyżej. Dla zdefiniuj jako liczbę automatów w które akceptują oba $n\ge1$ $DFA(n)$ $n^{2n}2^n$ $x,y\in\{0,1\}^*$ $K_n(x,y)$ $DFA(n)$ i . Pytanie: czy można obliczyć w czasie ? $x$ $y$ $K_n(x,y)$ $poly(n,|x|,|y|)$

— Aryeh
źródło

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

Aryeh, czy możesz wyjaśnić liczbę

? Nie mogę uzyskać współczynnika

. 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

; co odpowiada

. Określ zestaw stanów końcowych; to

n^{2 n} 2^{n}

$n^{2n} 2^n$

2^{n}

$2^n$

0

$0$

1

$1$

n^{2 n}

$n^{2n}$

2^{n}

$2^n$

— Srivatsan Narayanan

Rzeczywiście, nie obchodzi mnie, co stanie się z ciągami innymi niż

. Myślę, że potrzeba pewnej ilości punktów, aby rozpocząć nagrodę?

x

$x$

y

$y$

— Aryeh

Najmniejszy automat, który akceptuje

ma jeden stan, więc nie sądzę, aby był on bardzo pouczający ...

x

$x$

y

$y$

— Aryeh

Oto pomysł: musimy tylko znać liczbę

-state DFAS które kończą się w tym samym stanie na

. Niech liczba ta jest

jest całkowitą ilość DFAS, czyli

. Zatem odpowiedź brzmi

n

$n$

x

$x$

y

$y$

m

$m$

M

$M$

M = n^{2 n} 2^{n}

$M=n^{2n}2^{n}$

\frac{1}{2} m + \frac{1}{4} (M - m)

$\frac{1}{2}m + \frac{1}{4}(M-m)$

m

$m$

x

$x$

y

$y$

x = 0^{a}

$x=0^a$

b = 1^{b}

$b=1^b$

l

$l$

max {a, b}

$\max\{a,b\}$

0^{a}

$0^a$

1^{b}

$1^b$

m

$m$

Odpowiedzi:

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). $n$ $x$ $y$

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 . $K(x,y)$ $x$ $y$ $p$

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 . $p \ge 1/n$ $x$ $y$ $x$ $y=00$ $p= \frac{n+1}{(n-1)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? $x$ $y$ $n$ $n!$ $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=1577108

p o l y (n, | x |, | y |)

$poly(n,|x|,|y|)$

— Aryeh

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.

n

$n$

K_{n} (x, y)

$K_n(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

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: $n$ $K$

Na wejściu , gdzie $x$ $y$ $x,y\in\Sigma^*$

Przechowywać i $x$ $y$
zainicjuj licznik na $c$ $0$
dla każdego z Twoich DFA $n^{2n} 2^n$
za. symuluj to dla obu słów (ten krok to ) $\mathcal{O}(|xy|)$

b. przyrost jeśli oba przebiegi symulacji są akceptowane $c$
wyjście $c$

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

— Kai
źródło

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

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

$n$

— Lev Reyzin

Tak, dzięki za wskazanie luki, Kai. Zostało to naprawione :)

— Aryeh