Pengantar automata probabilistik

Di mana saya dapat menemukan pengantar untuk automata probabilistik dan apa yang mereka kenali (fungsi tertentu dari kata ke )? Apakah ada istilah standar untuk fungsi seperti itu yang dikenali oleh automata probabilistik, analog dengan "bahasa reguler" untuk apa yang dikenali deterministik finite automata (DFA)? $[0,1]$

Saya mencari sesuatu yang mendekatinya secara analog untuk mempelajari pertanyaan dasar tentang DFA dan bahasa reguler, seperti sifat ekspresif, penutupan, dan sifat decidability.

Ini dan ini sepertinya bukan yang saya cari.

reference-request fl.formal-languages probabilistic-automata Prateek
sumber

Mereka adalah "dukungan positif" dari seri

-rasional, yaitu bahasa

untuk

seri seperti itu. Ini tidak berperilaku terlalu baik. Saya mempelajari penutupan Boolean dari kelas ini, jika Anda tertarik: eccc.hpi-web.de/report/2013/040 .

Z

$\mathbb{Z}$

{w ∣ (r, w) > 0}

$\{w \mid (r, w) > 0\}$

r

$r$

Michaël Cadilhac

Jawaban:

Makalah pertama oleh Rabin (1963) memberikan dasar-dasar apa yang Anda cari. Kelas bahasa yang dikenali oleh automata probabilistik (dengan cutpoint) disebut bahasa stokastik.

$P$ $\Sigma$ $f_P(w)$ $P$ $w \in \Sigma^*$ $P$ $\lambda \in [0,1)$

$L(P,\lambda) = \{ w \in \Sigma^* \mid f_P(w) > \lambda \}$

Mengomentari bahwa pengakuan dengan cutpoint dapat dilihat sebagai pengakuan dengan kesalahan tak terbatas. Dalam hal error-terikat (atau cutpoint terisolasi) automata probabilistik dapat mengenali semua dan hanya bahasa biasa.

Buku karya Paz (1971) dan survei oleh Bukharaev (1980) adalah referensi yang bagus.

Anda juga dapat memeriksa survei terbaru tentang quantum automata di mana Anda dapat melacak beberapa referensi tentang automata probabilistik.

Abuzer Yakaryilmaz
sumber