Rozdzielanie słów losowymi DFA

Jeden z interesujących otwartych problemów dotyczących DFA wymienionych w Czy są jakieś otwarte problemy dotyczące DFA? jest wielkością DFA wymaganą do oddzielenia dwóch łańcuchów długości $n$ . Jestem ciekawy, czy są jakieś wyniki dotyczące zdolności losowego DFA do oddzielania dwóch podanych (nielosowych) ciągów.

Wyraźnie losowy DFA o wystarczająco wielu stanach oddziela łańcuchy z dużym prawdopodobieństwem. W szczególności, jeśli $u,v \in \Sigma^n$ , losowe DFA ze stanami $O(n)$ prawdopodobnie nigdy nie powrócą do tego samego stanu, gdy osiągnie pierwsze miejsce, w którym różnią się $u$ i $v$ , a zatem oddziela $u$ i $v$ .

Czy możemy zrobić lepiej? Idealnie, co jest najmniejszą ST, które losowym DFA z państw oddziela ciągi o długości z dodatnim prawdopodobieństwa (lub może prawdopodobieństwo )? Krótkie wyszukiwanie nie wykazało wielu wyników dotyczących właściwości losowych DFA; wszystko, co mogłem znaleźć, to http://arxiv.org/abs/1311.6830 . $f(n)$ $f(n)$ $n$ $\ge 1/2$

dfa random-graphs

— Geoffrey Irving
źródło

Pozytywne prawdopodobieństwo nie jest tutaj szczególnie przydatnym warunkiem, biorąc pod uwagę, że jest to tylko powtórzenie otwartego problemu. Wysokie prawdopodobieństwo wciąż może być interesujące.

— Geoffrey Irving

Co znaczy „separuje”? Akceptuje jedno, a odrzuca drugie? Jeśli tak, to czy oczywiste jest, że stany

wystarczające?

O (n)

$O(n)$

— usul

Tak, oddziela oznacza, że akceptuje dokładnie jeden. I masz rację: najbardziej trywialny argument separacji faktycznie wymaga stanów

(to, co napisałem powyżej jest błędny), choć byłbym zaskoczony, gdyby mniej było ich mniej.

O (n^{2})

$O(n^2)$

— Geoffrey Irving

Czy nie spodziewałbyś się, że granice będą zależeć od tego, jak bardzo różnią się słowa? Wygląda na to, że słowa różniące się pojedynczą literą byłyby trudniejsze do przypadkowego rozróżnienia, ponieważ musisz dyskryminować przy tym jednym przejściu, a bardzo różne słowa byłyby łatwiejsze. [Aby uogólnić, możesz zapomnieć o najdłuższym wspólnym prefiksie (z tego osiągasz stan losowy); następnie różne litery wysyłają cię do tego samego stanu lub do różnych stanów; wtedy, jeśli stany są różne, musisz przyjrzeć się proba ponownej synchronizacji i pozostania w synchronizacji (zaczyna się ponownie w zależności od słów) ...]

— ann

Tak, podobnie jak problem otwarty, interesują mnie najtrudniejsze możliwe słowa, aby je rozróżnić. Słowa, które różnią się tylko kilkoma miejscami, mogą już być oddzielone stanami

, więc jest mało prawdopodobne, aby były trudnym przypadkiem.

O (\log n)

$O(\log n)$

— Geoffrey Irving

[Edytuj: ta odpowiedź nie działa, zobacz komentarze.]

To tylko nieformalny pomysł i nie wiem, czy to pomaga, ale jest zbyt długi, aby go podać w komentarzu. Nie jestem też w ogóle zaznajomiony z przypadkowymi DFA, więc może mam błędną intuicję, jak powinieneś myśleć o prawdopodobieństwach na ich temat, ale mam nadzieję, że nie jest to całkowicie bezwartościowe.

Przypuszczam, że twoje granice powinny zależeć od tego, jak bardzo różnią się i ; jeśli nie, wydaje mi się jasne, że najgorszym przypadkiem są łańcuchy różniące się tylko pierwszym znakiem (łańcuchy różniące się w zbiorze pozycji mają większe szanse na rozróżnienie niż łańcuchy różniące się w zbiorze $u$ $v$ $X$ pozycji , Powiedziałbym, a jak najszybsze wprowadzenie różnicy daje możliwość ponownej synchronizacji). $Y \subset X$

Przyjrzę się również prawdopodobieństwu rozróżnienia słów, a mianowicie, że osiągają różne stany. Sądzę, że musiałbyś wtedy dostosować się do przyjęcia lub odrzucenia na podstawie tego, jak twoje losowe DFA przydzielają stany końcowe. Jeśli prawdopodobieństwo każdego stanu 1/2 jest ostateczne, wówczas gdy łańcuchy kończą się w tym samym stanie, nie są rozróżniane, a gdy kończą się w różnych stanach, prawdopodobieństwo 1/2 ich rozróżnienia.

Teraz rozważę słowo uzyskane z i w następujący sposób: jeśli , przeciwnym razie. Myślę, że jest jasne, że jest jedyną interesującą rzeczą do rozważenia na temat i . $w$ $u$ $v$ $w_i = 1$ $u_i = v_i$ $w_i = 0$ $w$ $u$ $v$

Teraz należy ustalić prawdopodobieństwo tego, że są w tym samym stanie po przeczytaniu prefiksów długości z i , a prawdopodobieństwo tego, że nie są. $p(i)$ $i$ $u$ $v$ $q(i) = 1 - p(i)$

Myślę, że mamy gdy wynosi . Intuicyjnie jesteśmy w tym samym stanie po przeczytaniu liter albo kiedy byliśmy w tym samym stanie po przeczytaniu , lub gdy byliśmy w dwóch różnych (losowych) stanach, narysowaliśmy dwie przejścia do stanów losowych, a one się zdarzyły bądź taki sam. Podobnie mamy $p(i+1) = p(i) + q(i)/n$ $w_{i+1}$ $1$ $i+1$ $i$ gdy wynosi $p(i+1) = 1/n$ $w_{i+1}$ $0$ : rysujesz dwa losowe stany, bez względu na to, od czego zacząłeś.

Z tego sądzę, że można obliczyć prawdopodobieństwo bycia w tym samym stanie po przeczytaniu i . $u$ $v$

— a3nm
źródło

Niestety nie jest wcale oczywiste, że

jest jedyną interesującą właściwością

. Najłatwiej to zobaczyć, ponieważ istnieje trywialnie niezerowe prawdopodobieństwo odróżnienia dowolnego nietrywialnego

; w rzeczywistości wystarczą tylko dwa stany, niezależnie od

. Jednak, jak omówiono w arxiv.org/pdf/1103.4513.pdf , istnieją słowa

długości

st no

stan DFA może je rozróżnić. Jest to sprzeczne z twoimi formułami dla

w

$w$

u

$u$

v

$v$

w

$w$

0^{n}

$0^n$

n

$n$

u, v

$u,v$

n

$n$

o (\log n)

$o(\log n)$

p (i)

$p(i)$ .

— Geoffrey Irving

Aby to wyjaśnić, twoje formuły byłyby poprawne, gdyby przejścia DFA były losową funkcją indeksu ciągu; ponieważ są one niezależne od wskaźnika, prawdopodobieństwa są skorelowane w dość skomplikowany sposób.

— Geoffrey Irving

Obawiam się, że nie rozumiem twojego kontrprzykładu. Istnieje

prba, z dwoma stanami, rozróżniającymi

, OK; i może są słowa o długości

, których nie można rozdzielić stanami

. Ale w jaki sposób przeczy to mojemu twierdzeniu, że

jest jedyną ważną rzeczą, lub moim formułom dla

> 0

$>0$

0^{n}

$0^n$

w \neq 0^{n}

$w \neq 0^n$

n

$n$

o (\log n)

$o(\log n)$

w

$w$

p (i)

$p(i)$ ? Jeśli chodzi o korelacje, widzę, że może istnieć hatchback, o którym wspominasz, ale nie rozumiem jeszcze, dlaczego zawodzi. Jeśli przejdziesz dwa razy przez ten sam stan, istnieje korelacja, ale czy istnieje powód, by sądzić, że wpłynie on średnio w określonym kierunku?

— a3nm

p (n) < 1

$p(n) < 1$ ,

u

$u$ and

v

$v$ are distinguished with positive probability. However, for sufficiently large

n

$n$ and small numbers of states we know that

p (n) = 1

$p(n) = 1$ for some

u

$u$ and

v

$v$ . Since your formulas imply that if

p (i) < 1

$p(i) < 1$ then

p (i + 1) = p (i) + (1 - p (i)) / n = p (i) (1 - 1 / n) + 1 / n < 1

$p(i+1) = p(i) + (1-p(i))/n = p(i)(1-1/n)+1/n < 1$ , your formula is not capturing the fact that certain

u

$u$ and

v

$v$ are impossible to distinguish.

— Geoffrey Irving

Ah... right, I understand. If no small DFA can distinguish two words, then no random DFA can distinguish them either. So indeed there is a problem with my approach, the probability

q (i)

$q(i)$ should drop to zero eventually, because of those correlations, it seems. Sorry for providing an incorrect answer.

— a3nm