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?
Jawaban:
Ada hasil baru-baru ini pada pac-learning polinomial set semilinear di LICS 2010: Parikh Gambar Bahasa Reguler: Kompleksitas dan Aplikasi . Saya kira ini bukan yang Anda cari.
Anda juga harus melihat ke makalah Clark dan Thollard: PAC-dapat dipelajari dari Probabilistic Deterministic Finite State Automata
sumber
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.
sumber