- 著者
-
但馬 康宏
富田 悦次
若月 光夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.97, no.356, pp.111-118, 1997-10-31
- 参考文献数
- 4
- 被引用文献数
-
1
単純決定性言語の多項式時間MAT学習に関する新たな結果を示す。一般に等価性質問は、仮説文法の入力に対して学習対象の言語との等価性を出力とし、さらに非等価の場合には、その根拠となる反例も出力となる。ここで、反例が正の反例の場合、さらに学習対象における導出構造を出力する質問を構造反例付き等価性質問と新たに定義する。このとき、任意の単純決定性言語は、単純決定性言語の族を用いて、所属性質問および構造反例付き等価性質問から多項式時間で厳密学習可能であることを示す。この学習アルゴリズムの基本的な考え方はAngluin (1987) によるアルゴリズムの拡張である。