| 講演名 | 2003/6/11 質問による文法推論アルゴリズムにおける等価性判定問題の一応用 但馬 康宏, 寺田 松昭, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本研究において,単純決定性言語,および正則言語を真に含む線形言語のある部分族に対して,所属性質問と代表記号列集合と呼ばれる正の例の集合を用いた学習アルゴリズムを示す.単純決定性言語は,終止記号つきの正則言語を真に含むため,上記2つの言語族はともに正則言語を含んだ言語族であるといえる.本アルゴリズムはどちらも,Angluinによる正則言語に対する所属性質問と反例による多項式時間学習アルゴリズムに基づき,観察表を用いて非終端記号数の小さな仮説文法を順次拡大する方法を用いる.ここで,非終端記号の候補が同一の非終端記号か否かは,ある終端記号列を生成可能か否かで決定される.本アルゴリズムでは,このような終端記号列を,複数の仮説文法に対して互いに等価性判定を行うことにより得ている点が特徴である. |
| 抄録(英) | We show two learning algorithms via membership queries and a representative sample; one for the class of simple deterministic languages and the other for a sub-class of linear languages. Here, the sub-class of linear languages contains that of regular languages and the class of simple deterministic languages contains that of regular languages with an end marker. Both of our algorithms increases the number of nonterminals of a hypothesis based on an observation table introduced by Angluin. In our algorithm, two candidates for nonterminals are distiguished by derivations about some special words. These words are gathered by compareing some hypothesis grammars each other. |
| キーワード(和) | 文法推論 / 質問による学習 / 観察表 / 文脈自由文法 / 等価性判定問題 |
| キーワード(英) | grammatical inference / learning via queries / observation table / context-free grammar / equivalence |
| 資料番号 | COMP2003-22 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/6/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 質問による文法推論アルゴリズムにおける等価性判定問題の一応用 |
| サブタイトル（和） | |
| タイトル（英） | An application of an eaui valence checking Droblem for a grammatica |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 文法推論 / grammatical inference |
| キーワード(2)（和/英） | 質問による学習 / learning via queries |
| キーワード(3)（和/英） | 観察表 / observation table |
| キーワード(4)（和/英） | 文脈自由文法 / context-free grammar |
| キーワード(5)（和/英） | 等価性判定問題 / equivalence |
| 第 1 著者 氏名（和/英） | 但馬 康宏 / Yasuhiro TAJIMA |
| 第 1 著者 所属（和/英） | 東京農工大学情報コミュニケーションエ学科 Department of Computer, Information and Communication Sciences, Tokyo Univ. of Agri. & Tech. |
| 第 2 著者 氏名（和/英） | 寺田 松昭 / Matsuaki TERADA |
| 第 2 著者 所属（和/英） | 東京農工大学情報コミュニケーションエ学科 Department of Computer, Information and Communication Sciences, Tokyo Univ. of Agri. & Tech. |
| 発表年月日 | 2003/6/11 |
| 資料番号 | COMP2003-22 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 119 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |