Bahasa reguler dan kompleksitas komunikasi konstan

Biarkan menjadi bahasa, dan mendefinisikan oleh jika dan hanya jika . Saya mencari referensi untuk: $L \subseteq A^*$ $f_L\colon A^* \times A^* \to \{0, 1\}$ $f_L(x, y) = 1$ $x\cdot y \in L$

Dalil. adalah biasa IFF kompleksitas komunikasi deterministik adalah konstan. $L$ $f_L$

$L$ $P$ $f_L$

n \mapsto max {comm (P, x, y) : | x \cdot y | = n}

$n \mapsto \max\{\text{comm}(P, x, y) : |x\cdot y| = n\}$

comm (P, x, y)

$\text{comm}(P, x, y)$

x

$x$

y

$y$

P

$P$

Satu-satunya tempat aku bisa menemukan yang ada di George Hauser tesis PhD, tahun 1989, tersedia di sini , di mana ia juga generalizes bahwa untuk distro lain dari input antara Alice dan Bob, sehingga jumlah "luka" adalah konstan. $x\cdot y$

reference-request communication-complexity regular-language Michaël Cadilhac
sumber

Ambil bahasa yang tidak teratur, dan tentukan . Maka memiliki kompleksitas komunikasi , tetapi tentu saja tidak teratur. Apa yang saya lewatkan?

C

$C$

L = {c \circ r : c \in C, r \in {0, 1}^{| c |}}

$L = \{c \circ r : c \in C, r \in \{0,1\}^{|c|} \}$

L

$L$

O (1)

$O(1)$

Igor Shinkar

@IgorShinkar: Saya tidak yakin saya mendapatkan persis apa yang Anda tulis di sana, tetapi Anda tampaknya mengisyaratkan bukti klasik bahwa setiap bahasa dengan satu kata per panjang dapat diubah menjadi bahasa dengan kompleksitas komunikasi yang konstan. Namun, ini mengasumsikan bahwa Alice dan Bob menerima persis setengah dari kata yang diuji; di sini, tidak ada asumsi seperti itu, dan, dengan cara yang berlawanan, mereka harus menyelesaikan masalah dengan adanya pemisahan input. Apakah itu menjawab pertanyaan Anda?

Michaël Cadilhac

Oh begitu. Jadi jika untuk setiap split CC adalah konstan maka adalah reguler.

L

$L$

Igor Shinkar

Jawaban:

Untuk , Anda memiliki "Kompleksitas Komunikasi", Eyal Kushilevitz dalam Kemajuan dalam Komputer, Volume 44, 1997 ( http://www.sciencedirect.com/science/article/pii/S0065245808603423 ). $\Rightarrow$

Anda juga dapat menemukan bagian "Kompleksitas Komunikasi dan Hierarki Chomsky" dalam buku "Kompleksitas Komunikasi dan Komputasi Paralel" oleh Juraj Hromkovič di mana terbukti. Mungkin juga terbukti di suatu tempat di buku ini tetapi saya gagal menemukannya di sini. Hal terdekat yang tampaknya ada adalah Latihan 5.2.5.2 tetapi, ini hanya latihan (lihat seluruh Bab 5 juga, yang secara ekstensif mempelajari otomat terbatas tetapi saya tidak berpikir itu secara eksplisit menjawab pertanyaan Anda). $\Leftarrow$

Untuk apa nilainya, bukti dari kedua arah terlihat mudah jadi saya pikir jika Anda membutuhkannya di kertas Anda dapat membuat sketsa dengan cepat: untuk , ambil otomat terbatas untuk dan amati bahwa cukup bagi Alice untuk berkomunikasi keadaan yang dia capai setelah membaca bagian inputnya. Kemudian Bob menyelesaikan simulasi di automata. Untuk , jika Anda memiliki protokol yang dibatasi oleh konstanta, maka memiliki jumlah hasil terbatas yang merupakan karakterisasi terkenal dari bahasa reguler . $\Rightarrow$ $L$ $\Leftarrow$ $L$ $w^{-1}L = \{u : wu \in L\}$

serigala
sumber

Terima kasih banyak atas masukan Anda. Saya setuju bahwa ini adalah hasil yang mudah, dan alami pada saat itu, dan mungkin harus dianggap sebagai cerita rakyat. Saya tahu dua referensi yang Anda berikan dengan cukup baik, pada kenyataannya, dan, seperti yang Anda lakukan, tidak dapat menemukan protokol yang saya pertimbangkan di atas. Karena pertanyaan ini adalah "permintaan referensi", saya khawatir saya tidak dapat menerima jawaban Anda pada saat ini.

Michaël Cadilhac

Saya tahu, tetapi terlalu lama untuk berkomentar dan saya pikir masih layak untuk disebutkan bahwa setidaknya satu cara terbukti secara eksplisit dalam literatur. Saya beri tahu Anda jika saya menemukan bukti!

Serigala

Sangat menghargai! :-)

Michaël Cadilhac