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|)$

cc.complexity-theory fl.formal-languages automata-theory counting-complexity 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