Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Learning of Elementary Formal Systems with Two Clauses Using Queries Pembelajaran Sistem Formal Asas dengan Dua Klausa Menggunakan Pertanyaan

Hirotaka KATO, Satoshi MATSUMOTO, Tetsuhiro MIYAHARA

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Sistem formal asas, singkatannya EFS, ialah sejenis program logik atas rentetan, dan dianggap sebagai satu set peraturan untuk menjana bahasa. Untuk EFS Γ, bahasa L(Γ) menandakan set semua rentetan yang dihasilkan oleh Γ. Kami menganggap bentuk EFS baharu, dipanggil EFS dua fasal terhad, dan menandakan dengan rEFS set semua EFS dua fasal terhad. Kemudian kita mengkaji kebolehbelajaran rEFS dalam model pembelajaran yang tepat. Kelas rEFS mengandungi kelas corak biasa, yang dipelajari secara meluas dalam Teori Pembelajaran. Biarkan Γ* menjadi sasaran EFS dalam rEFS daripada pembelajaran. Dalam model pembelajaran yang tepat, oracle untuk pertanyaan superset menjawab "yes" untuk input EFS Γ dalam rEFS if L(Γ) ialah superset bagi L*), dan mengeluarkan rentetan masuk L*)-L(Γ), jika tidak. Oracle untuk pertanyaan keahlian menjawab "yes" untuk rentetan input w if w termasuk dalam L*), dan jawapan "tidak", jika tidak. Kami menunjukkan bahawa mana-mana EFS dalam rEFS betul-betul boleh dikenal pasti dalam masa polinomial menggunakan pertanyaan keahlian dan superset. Selain itu, untuk jenis pertanyaan lain, kami menunjukkan bahawa tiada algoritma pembelajaran masa polinomial untuknya rEFS dengan menggunakan pertanyaan. Keputusan ini menunjukkan kekerasan pembelajaran kelas rEFS dalam model pembelajaran yang tepat, secara amnya.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.172-180
Tarikh penerbitan
2009/02/01
Diumumkan
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.E92.D.172
Jenis Manuskrip
Special Section PAPER (Special Section on Foundations of Computer Science)
kategori

Pengarang

Kata kunci

Contents [show]