Apakah ada keluarga bahasa formal yang diketahui benar-benar PAC bisa dipelajari?

9

Secara khusus saya maksudkan keluarga bahasa yang menerima string panjang yang sewenang-wenang - bukan konjungsi atas n bit atau daftar keputusan atau bahasa "sederhana" lainnya yang terkandung dalam {0,1} ^ n.

Saya bertanya tentang bahasa reguler "automata-theoretic" sebagai lawan dari bahasa "logic-theoretic": sesuatu seperti bahasa yang dapat diuji secara terpisah, bahasa dengan ketinggian mulai nol, bahasa yang dapat diuji secara lokal, hal-hal semacam itu. Parameter kompleksitas yang relevan n adalah ukuran DFA penerimaan minimal. Jadi, singkatnya: adakah keluarga DFA n-state yang menarik yang diketahui sebagai PAC yang dapat dipelajari secara efisien?

Aryeh
sumber
1
apakah Anda telah melihat pertanyaan terkait: cstheory.stackexchange.com/questions/1401/… dan cstheory.stackexchange.com/questions/153/… , serta jawaban ini
Suresh Venkat
1
pertanyaan ini mungkin juga relevan: cstheory.stackexchange.com/questions/1854
Lev Reyzin

Jawaban:

1

Makalah ini memberikan petunjuk yang baik tentang hasil pembelajaran PAC untuk bahasa lain: Belajar Bahasa yang Dipisahkan Secara Linier

Karya Clark & ​​Thollard disempurnakan oleh Castro & Gavalda dengan cara yang sesuai dengan apa yang Anda cari: Menuju PAC-learning probabilistic deterministic finit automata automata yang terbatas

Dan karya ini adalah jawaban yang baik dari pertanyaan awal: Tentang Learnability of Shuffle Ideal . Salah satu penulis kemungkinan adalah orang yang sama yang sebelumnya mengajukan pertanyaan di sini, tetapi saya menemukan halaman ini dengan mengerjakan masalah itu dan baru saja menemukan makalah ini: mungkin membantu orang lain untuk memiliki referensi ini.

pengguna14249
sumber
3
Dugaan saya adalah bahwa @Aryeh mengetahui setidaknya dua dari makalah ini :)
Lev Reyzin
Memang, saya samar-samar ingat penulis bersama # 1 dan # 3 ... Tidak ada yang memberikan hasil PAC positif dari jenis yang saya tanyakan. Di # 1, kami memerlukan margin, yang merupakan kuantitas yang bergantung pada distribusi. Di # 3, kami memberikan hasil negatif yang kuat.
Aryeh