Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample

スポンサーリンク

概要

• 論文の詳細を見る

• We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.

• 社団法人電子情報通信学会の論文
• 2000-04-25

著者

• Tajima Y

  The Authors Are With The Graduate School Of Electro-communications The University Of Electro-communi

• Tomita Etsuji

  The Authors Are With The Graduate School Of Electro-communications The University Of Electro-communi

• TAJIMA Yasuhiro

  The authors are with the Graduate School of Electro-Communications, The University of Electro-Commun

• WAKATSUKI Mitsuo

  The authors are with the Graduate School of Electro-Communications, The University of Electro-Commun

• Wakatsuki Mitsuo

  The Authors Are With The Graduate School Of Electro-communications The University Of Electro-communi

関連論文

• Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample

スポンサーリンク