Batas pada ukuran NFA terkecil untuk L_k-berbeda

Pertimbangkan bahasa $L_{k-distinct}$ yang terdiri dari semua $k$ -surat string lebih $\Sigma$ sehingga tidak ada dua huruf yang sama:

L_{k - d i s t i n c t} := {w = σ_{1} σ_{2} . . . σ_{k} ∣ \forall i \in [k] : σ_{i} \in Σ and \forall j \neq i : σ_{j} \neq σ_{i}}

$L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$

Bahasa ini terbatas dan karenanya teratur. Khususnya, jika $\left|\Sigma\right|=n$ , lalu. $\left|L_{k-distinct}\right| = \binom{n}{k} k!$

Apakah otomat terbatas non-deterministik terkecil yang menerima bahasa ini?

Saat ini saya memiliki batasan longgar atas dan bawah:

NFA terkecil yang dapat saya buat memiliki menyatakan. $4^{k(1+o(1))}\cdot polylog(n)$
Lemma berikut menyiratkan batas bawah status : $2^k$

Biarkan $L ⊆ Σ^*$ menjadi bahasa biasa. Misalkan ada $n$ pasangan $P = \{ (x_i, w_i) \mid 1 ≤ i ≤ n \}$ sehingga $x_i\cdot w_j \in L$ jika dan hanya jika $i=j$ . Maka setiap NFA yang menerima L memiliki setidaknya n status.

Batas bawah (sepele) lainnya adalah $log$ $n\choose k$ , yang merupakan log dengan ukuran DFA terkecil untuk bahasa tersebut.

Saya juga tertarik pada NFA yang hanya menerima sebagian kecil ( $0<\epsilon<1$ ) dari $L_{k-distinct}$ , jika ukuran automaton lebih kecil dari $\epsilon\cdot 4^{k(1+o(1))}\cdot polylog (n)$ .

Sunting: Saya baru saja memulai karunia yang memiliki kesalahan dalam teks.

Maksud saya, kita dapat mengasumsikan $k=polylog(n)$ sementara saya menulis $k=O(log(n))$ .

Sunting2:

Karunia akan segera berakhir, jadi jika ada yang tertarik dengan cara yang mungkin lebih mudah untuk mendapatkannya, pertimbangkan bahasa berikut:

$L_{(r,k)-distinct} :=\{w : w$ berisi $k$ simbol yang berbeda dan tidak ada simbol yang muncul lebih dari $r$ kali $\}$ .

(Yaitu $L_{(1,k)-distinct} = L_{k-distinct}$ ).

Konstruksi yang mirip dengan yang ada di komentar memberikan otomat berukuran untuk . $O(e^k\cdot 2^{k\cdot log(1+r)}\cdot poly(n))$ $L_{(r,k)-distinct}$

Bisakah ini diperbaiki? Apa batas bawah terbaik yang bisa kami tunjukkan untuk bahasa ini?

automata-theory lower-bounds regular-language communication-complexity streaming BPR
sumber

Bisakah Anda menggambarkan NFA batas atas Anda?

mjqxxxx

Saya belum bisa menulisnya karena kami masih mengerjakannya, dan belum menyelesaikan buktinya. Sebagai gantinya, saya akan menjelaskan otomat yang jauh lebih sederhana dari ukuran : Ambil keluarga hash sempurna . Setiap hash tersebut adalah fungsi . Ini berarti bahwa untuk setiap subset dari ukuran paling banyak , ada fungsi sehingga memetakan setiap item dari subset ke nomor yang berbeda. Setelah hashing, alfabet yang dihasilkan memiliki huruf , karenanya autumaton ukuran dapat menerima bahasa .

O ((2 e)^{k} * 2^{O (l o g (k))} * l o g (n))

$O((2e)^k * 2^{O(log(k))} * log(n))$

(n, k)

$(n,k)$

H

$H$

h : [n] \to [k]

$h: [n] \to [k]$

[n]

$[n]$

k

$k$

h \in H

$h\in H$

k

$k$

2^{k}

$2^k$

L_{k - d i s t i n c t}

$L_{k-distinct}$

BPR

Batas bawah memberi hanya menghitung jumlah status bahwa NFA dapat berada setelah persis langkah . Saya tidak berpikir bahwa saya mengetahui adanya metode pembuktian yang memberikan batasan yang jauh lebih baik untuk ukuran total daripada apa yang bisa diperoleh daripada hanya dengan melihat apa yang terjadi setelah langkah , untuk beberapa . Tapi di sini, untuk setiap ada NFA yang hanya bisa berada dalam satu setelah persis menyatakan.

(2 - o (1))^{k}

$(2-o(1))^k$

k / 2

$k/2$

t

$t$

t

$t$

t

$t$

(2 + o (1))^{k}

$(2+o(1))^k$

t

$t$

Noam

Bukti (dari klaim saya sebelumnya): Kasus tersulit adalah ; memilih yang berbeda subset acak (dari simbol alfabet) ukuran persis masing-masing dan membangun sebuah NFA yang memiliki negara untuk setiap dengan beberapa jalan menuju ke sana IFF pertama simbol semua berbeda dan yang terkandung dalam , dan memiliki jalur menerima dari itu IFF berikut simbol semua berbeda dan yang terkandung dalam komplemen dari . Argumen penghitungan akan menunjukkan whp (atas pilihan acak

t = k / 2

$t=k/2$

2^{k} \cdot p o l y (k, \log n)

$2^k \cdot poly(k, \log n)$

S_{i}

$S_i$

n

$n$

t

$t$

i

$i$

t

$t$

S_{i}

$S_i$

k - t

$k-t$

S_{i}

$S_i$

S_{i}

$S_i$ NFA ini memang akan menerima semua bahasa yang diinginkan.

Noam

Dalam konstruksi sebelumnya, cara paling sederhana untuk membangun NFA akan memiliki status untuk setiap kemungkinan awalan panjang dan untuk setiap akhiran panjang yang mungkin . Sebaliknya, bagian awalan dan bagian akhiran dari NFA dapat dibangun secara rekursif menggunakan konstruksi acak yang sama (tapi masing-masing sekarang hanya dalam dan pelengkapnya) dan ini akan memberikan ukuran total .

j < t

$j < t$

j > k - t

$j > k-t$

S_{i}

$S_i$

(4 + o (1))^{k}

$(4+o(1))^k$

Noam

Jawaban:

Ini bukan jawaban tetapi metode yang saya percaya akan meninggalkan batas bawah yang lebih baik. Mari kita memotong masalah setelah surat yang dibaca. Menunjukkan keluarga unsur set oleh dan keluarga elemen set oleh . Nyatakan status yang dapat dijangkau setelah membaca elemen (dalam urutan apa pun) oleh dan status dari mana status penerima dapat dicapai setelah membaca elemen (dalam urutan apa pun) oleh . Kita membutuhkan jika dan hanya jika $a$ $a$ $[n]$ $\mathcal A$ $b=k-a$ $[n]$ $\mathcal B$ $A$ $S_A$ $B$ $T_B$ $S_A\cap T_B\ne \emptyset$ $A\cap B=\emptyset$ . Ini sudah memberikan batas bawah untuk jumlah negara yang diperlukan dan saya pikir itu bisa memberikan sesuatu yang non-sepele.

Masalah ini pada dasarnya meminta batas bawah pada jumlah simpul dari sebuah hypergraph yang grafik garisnya (sebagian) diketahui. Masalah serupa dipelajari misalnya, oleh Bollobas dan ada beberapa metode bukti yang diketahui yang dapat berguna.

Pembaruan 2014.03.24: Sebenarnya jika hypergraph di atas dapat direalisasikan pada simpul , maka kita juga mendapatkan protokol kompleksitas komunikasi non-deterministik panjang untuk mengatur disjointness dengan input set ukuran dan (sebenarnya keduanya masalahnya setara). Kemacetan tentu saja ketika , untuk ini saya hanya bisa menemukan yang berikut dalam buku Eyal dan Noam: dibuktikan oleh argumen probabilistik standar. Sayangnya saya tidak bisa (belum) menemukan batas bawah yang cukup baik pada masalah ini tetapi dengan asumsi di atas tajam, itu akan memberikan batas bawah $s$ $\log s$ $a$ $b$ $a=b=k/2$ $N^1(DISJ_a)\le \log \big(2^k \log_e {n\choose a}\big)$ $\Omega(2^k\log n)$ menyatukan dua batas bawah yang telah Anda sebutkan.

domotorp
sumber

Terima kasih @domotorp atas jawaban Anda. Ini tampaknya sangat mirip dengan bukti lemma yang saya gunakan untuk batas bawah dalam pertanyaan awal, tetapi tanpa menentukan dan , dan dengan demikian bukan batas yang dapat dihitung. Komentar Anda pada pertanyaan di atas menunjukkan bahwa ikatan tidak dapat ditingkatkan dengan metode itu, apakah menurut Anda ini bisa lebih baik?

x_{i}

$x_i$

y_{i}

$y_i$

2^{k}

$2^k$

Inti dari komentar saya di atas adalah bahwa teknik-teknik ini tidak dapat memberikan batas bawah di atas . Inilah yang membuat masalah ini menarik bagi saya.

(2 + o (1))^{k}

$(2+o(1))^k$

Noam

@Noam: Misalkan k = 2, a = b = 1. Sudah maka kita mendapatkan batas bawah karena setiap harus berbeda.

\log n

$\log n$

S_{A}

$S_A$

domotorp

@domotorp: The menyembunyikan faktor : Berikut adalah analisis untuk kasus terburuk di mana : Mulai dengan dan tetap dan pilih secara acak subset dari huruf maka kita memiliki . Sekarang pilih set seperti itu secara acak maka probabilitas bahwa untuk setidaknya satu dari ini terjadi adalah . Jika kita memilih maka kita mendapatkan whp ini demikian untuk SEMUA set saling terpisah dan (ukuran

o (1)

$o(1)$

O (k \log n)

$O(k\log n)$

a = b = k / 2

$a=b=k/2$

A

$A$

B

$B$

S

$S$

n

$n$

P r [A \subseteq S a n d B \subseteq S^{c}] = 2^{- k}

$Pr[A \subseteq S \:and\: B \subseteq S^c]=2^{-k}$

r 2^{k}

$r2^k$

1 - e x p (- r)

$1-exp(-r)$

r = O (\log (\binom{n}{k})) = O (k \log n)

$r = O(\log {n \choose k}) = O(k \log n)$

A

$A$

B

$B$

k / 2

$k/2$ ). Jumlah total seperti dalam konstruksi ini adalah .

S

$S$

O (2^{k} k \log n)

$O(2^k k \log n)$

Noam

@Noam: Saya minta maaf tapi saya belum pernah melihat disembunyikan di dalam , terutama karena masalah ini juga menarik imho untuk . Tetapi Anda benar bahwa BPR bertanya tentang .

\log n

$\log n$

o (1)

$o(1)$

k << \log n

$k<<\log n$

k = p o l y l o g n

$k=polylog n$

domotorp

Beberapa pekerjaan dalam proses:

Saya mencoba membuktikan batas bawah . Berikut adalah pertanyaan yang saya yakin akan memberikan batas yang lebih rendah: temukan minimum sehingga ada fungsi yang menjaga disjointness, yaitu iff . Saya cukup yakin bahwa batas bawah akan segera menyiratkan batas bawah untuk masalah kita. kasar sesuai dengan set node yang NFA dapat dapatkan setelah membaca simbol pertama dari input, ketika himpunan $4^k$ $t$ $f:\{S \subseteq [n], |S|=k/2 \} \rightarrow \{0,1\}^t$ $S_1 \cap S_2 = \emptyset$ $f(S_1) \cap f(S_2) = \emptyset$ $t \ge 2k$ $2^{2k}=4k$ $f(S)$ $k/2$ $k/2$ simbol adalah . $S$

Saya pikir solusi untuk pertanyaan ini mungkin sudah diketahui, baik dalam literatur kompleksitas komunikasi (terutama dalam makalah yang berurusan dengan masalah ketidakjelasan; mungkin beberapa argumen peringkat matriks akan membantu), atau dalam literatur tentang pengkodean (misalnya seperti ini ).

pangsit mobius
sumber

Komentar saya di atas menunjukkan bahwa pendekatan ini tidak dapat mengalahkan

(2 + o (1))^{n}

$(2+o(1))^n$

Noam