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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Hirotaka KATO, Satoshi MATSUMOTO, Tetsuhiro MIYAHARA, "Learning of Elementary Formal Systems with Two Clauses Using Queries" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 172-180, February 2009, doi: 10.1587/transinf.E92.D.172.
Abstract: An elementary formal system, EFS for short, is a kind of logic program over strings, and regarded as a set of rules to generate a language. For an EFS Γ, the language L(Γ) denotes the set of all strings generated by Γ. We consider a new form of EFS, called a restricted two-clause EFS, and denote by rEFS the set of all restricted two-clause EFSs. Then we study the learnability of rEFS in the exact learning model. The class rEFS contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in rEFS of learning. In the exact learning model, an oracle for superset queries answers "yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L(Γ*), and outputs a string in L(Γ*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L(Γ*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.172/_p
Salinan
@ARTICLE{e92-d_2_172,
author={Hirotaka KATO, Satoshi MATSUMOTO, Tetsuhiro MIYAHARA, },
journal={IEICE TRANSACTIONS on Information},
title={Learning of Elementary Formal Systems with Two Clauses Using Queries},
year={2009},
volume={E92-D},
number={2},
pages={172-180},
abstract={An elementary formal system, EFS for short, is a kind of logic program over strings, and regarded as a set of rules to generate a language. For an EFS Γ, the language L(Γ) denotes the set of all strings generated by Γ. We consider a new form of EFS, called a restricted two-clause EFS, and denote by rEFS the set of all restricted two-clause EFSs. Then we study the learnability of rEFS in the exact learning model. The class rEFS contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in rEFS of learning. In the exact learning model, an oracle for superset queries answers "yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L(Γ*), and outputs a string in L(Γ*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L(Γ*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general.},
keywords={},
doi={10.1587/transinf.E92.D.172},
ISSN={1745-1361},
month={February},}
Salinan
TY - JOUR
TI - Learning of Elementary Formal Systems with Two Clauses Using Queries
T2 - IEICE TRANSACTIONS on Information
SP - 172
EP - 180
AU - Hirotaka KATO
AU - Satoshi MATSUMOTO
AU - Tetsuhiro MIYAHARA
PY - 2009
DO - 10.1587/transinf.E92.D.172
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - An elementary formal system, EFS for short, is a kind of logic program over strings, and regarded as a set of rules to generate a language. For an EFS Γ, the language L(Γ) denotes the set of all strings generated by Γ. We consider a new form of EFS, called a restricted two-clause EFS, and denote by rEFS the set of all restricted two-clause EFSs. Then we study the learnability of rEFS in the exact learning model. The class rEFS contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in rEFS of learning. In the exact learning model, an oracle for superset queries answers "yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L(Γ*), and outputs a string in L(Γ*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L(Γ*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general.
ER -