Dana Angluin ( 1987 ; pdf ) mendefinisikan model pembelajaran dengan pertanyaan keanggotaan dan pertanyaan teori (berlawanan dengan contoh fungsi yang diusulkan). Dia menunjukkan bahwa bahasa reguler yang diwakili oleh DFA minimal negara dapat dipelajari dalam waktu polinomial (di mana fungsi yang diusulkan adalah DFA) dengan keanggotaan-kueri dan paling banyak teori-kueri ( adalah ukuran contoh tandingan terbesar yang disediakan oleh tutor). Sayangnya, dia tidak membahas batas bawah.
Kita dapat menggeneralisasi model sedikit dengan mengasumsikan guru les magis yang dapat memeriksa kesetaraan antara fungsi arbitrer dan memberikan contoh tandingan jika berbeda. Kemudian kita dapat bertanya seberapa sulit untuk belajar kelas yang lebih besar daripada bahasa biasa. Saya tertarik dengan generalisasi ini dan pembatasan asli untuk bahasa reguler.
Adakah batas bawah yang diketahui tentang jumlah kueri dalam model keanggotaan dan contoh-balik?
Saya tertarik pada batas bawah pada jumlah pertanyaan keanggotaan, pertanyaan teori, atau pertukaran antara keduanya. Saya tertarik pada batas bawah untuk setiap kelas fungsi, bahkan untuk kelas yang lebih rumit daripada bahasa biasa.
Jika tidak ada batas bawah: Apakah ada barier yang dikenal untuk membuktikan kueri batas bawah dalam model ini?
Pertanyaan-pertanyaan Terkait
Apakah ada peningkatan pada algoritma Dana Angluin untuk mempelajari set reguler
sumber