Memisahkan kata-kata dengan DFA acak

Salah satu masalah terbuka yang menarik tentang DFA yang terdaftar di Apakah ada masalah terbuka yang tersisa tentang DFA? adalah ukuran DFA yang diperlukan untuk memisahkan dua string panjang $n$ . Saya ingin tahu apakah ada hasil tentang kemampuan DFA acak untuk memisahkan dua string (nonrandom) yang diberikan.

Jelas DFA acak dengan banyak negara cukup memisahkan string dengan probabilitas tinggi. Secara khusus, jika $u,v \in \Sigma^n$ , DFA acak dengan status $O(n)$ tidak mungkin untuk mengunjungi kembali kondisi yang sama setelah mencapai tempat pertama di mana $u$ dan $v$ berbeda, dan oleh karena itu memisahkan $u$ dan $v$ .

Bisakah kita berbuat lebih baik? Idealnya, apa yang terkecil st bahwa DFA acak dengan string negara memisahkan panjang dengan probabilitas positif (atau mungkin probabilitas )? Pencarian singkat tidak menghasilkan banyak hasil pada properti DFA acak; yang bisa saya temukan adalah http://arxiv.org/abs/1311.6830 . $f(n)$ $f(n)$ $n$ $\ge 1/2$

dfa random-graphs Geoffrey Irving
sumber

Probabilitas positif bukanlah kondisi yang sangat berguna di sini, mengingat itu hanyalah pernyataan ulang dari masalah terbuka. Peluang tinggi mungkin masih menarik.

Geoffrey Irving

Apa artinya "memisahkan"? Menerima satu dan menolak yang lain? Jika demikian, apakah jelas bahwa

menyatakan cukup?

O (n)

$O(n)$

usul

Ya, memisahkan berarti menerima tepat satu. Dan Anda benar: argumen pemisahan paling sepele sebenarnya membutuhkan

menyatakan (apa yang saya tulis di atas salah), meskipun saya akan terkejut jika lebih sedikit yang tidak mencukupi.

O (n^{2})

$O(n^2)$

Geoffrey Irving

Tidakkah Anda berharap batas tergantung pada seberapa jauh perbedaan kata-katanya? Sepertinya kata-kata yang berbeda dengan satu huruf akan lebih sulit untuk dibedakan secara acak, karena Anda perlu membedakan pada satu transisi itu, dan kata-kata yang sangat berbeda akan lebih mudah. [Untuk menggeneralisasi, Anda bisa melupakan awalan umum terpanjang (Anda mencapai keadaan acak dari itu); kemudian, berbagai surat mengirim Anda ke negara yang sama atau ke negara yang berbeda; maka jika statusnya berbeda, Anda perlu melihat kemungkinan penyinkronan, dan tetap sinkron (mulai tergantung lagi pada kata-kata) ...]

a3nm

Ya, seperti masalah terbuka, saya tertarik pada kata-kata yang paling sulit untuk didiskriminasi. Kata-kata yang berbeda hanya dalam beberapa tempat sudah dapat dipisahkan oleh status

, sehingga tidak mungkin menjadi hard case.

O (\log n)

$O(\log n)$

Geoffrey Irving

[Sunting: jawaban ini tidak berfungsi, lihat komentar.]

Ini hanya ide informal dan saya tidak tahu apakah itu membantu, tetapi terlalu lama untuk diberikan sebagai komentar. Juga, saya sama sekali tidak akrab dengan DFA acak, jadi mungkin saya memiliki intuisi yang salah tentang bagaimana Anda harus mempertimbangkan probabilitas pada mereka, tetapi mudah-mudahan ini tidak sepenuhnya tidak berharga.

Saya akan mengira bahwa batasan Anda harus bergantung pada seberapa besar perbedaan dan ; jika tidak, jelas bagi saya bahwa kasus terburuk adalah string berbeda hanya dengan karakter pertama mereka (string berbeda pada set posisi memiliki lebih banyak peluang untuk dibedakan daripada string berbeda pada set posisi , Saya katakan, dan menempatkan perbedaan sedini mungkin memberi Anda kesempatan untuk melakukan sinkronisasi ulang). $u$ $v$ $X$ $Y \subset X$

Saya juga akan melihat probabilitas bahwa kata-kata dibedakan, yaitu, mereka mencapai keadaan yang berbeda. Saya kira Anda kemudian perlu beradaptasi agar diterima atau ditolak berdasarkan bagaimana DFA acak Anda mengalokasikan status akhir. Jika setiap negara bagian memiliki probabilitas 1/2 menjadi final, maka ketika string berakhir pada keadaan yang sama mereka tidak dibedakan, dan ketika mereka berakhir di negara yang berbeda mereka memiliki probabilitas 1/2 dibedakan.

Sekarang saya akan mempertimbangkan kata diperoleh dari dan sebagai berikut: jika , dan sebaliknya. Saya pikir jelas bahwa adalah satu-satunya hal yang menarik untuk dipertimbangkan tentang dan . $w$ $u$ $v$ $w_i = 1$ $u_i = v_i$ $w_i = 0$ $w$ $u$ $v$

Sekarang, tentukan probabilitas bahwa kita berada pada keadaan yang sama setelah membaca awalan panjang dari dan , dan probabilitas bahwa kita tidak. $p(i)$ $i$ $u$ $v$ $q(i) = 1 - p(i)$

Saya pikir kita memiliki ketika adalah . Secara intuitif, kita berada dalam keadaan yang sama setelah membaca huruf baik ketika kita berada di keadaan yang sama setelah membaca , atau ketika kita berada di dua negara (acak) yang berbeda, kita menggambar dua transisi ke keadaan acak, dan mereka kebetulan menjadi sama. Demikian juga, kita memiliki $p(i+1) = p(i) + q(i)/n$ $w_{i+1}$ $1$ $i+1$ $i$ $p(i+1) = 1/n$ when $w_{i+1}$ is $0$ : you are drawing two random states, no matter where you started from.

From this I think you could compute the probability of being at the same state after reading $u$ and $v$ .

a3nm
sumber

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

To clarify, your formulas would be correct if the DFA transitions were a random function of the string index; since they are independent of index, the probabilities are correlated in a rather complicated fashion.

Geoffrey Irving

I'm afraid I don't get your counterexample. There is a

> 0

$>0$ prba, with two states, of distinguishing

0^{n}

$0^n$ and

w \neq 0^{n}

$w \neq 0^n$ , OK; and maybe there are words of length

n

$n$ that cannot be told apart with

o (\log n)

$o(\log n)$ states. But how does it contradict my claim that

w

$w$ is the only important thing, or my formulae for

p (i)

$p(i)$ ? As for correlations, I see there might be a catch of the kind you're mentioning but I don't understand yet why it fails exactly. If you go twice through the same state, there is a correlation, but is there a reason to think it would influence in a certain direction on average?

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

Memisahkan kata-kata dengan DFA acak

Jawaban: