| 講演名 | 2001/7/9 正則言語のある部分クラスに対する正の例からの多項式時間極限同定 吉成 智和, 富田 悦次, 若月 光夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | Pitt(1989)による多項式時間極限同定の定義では, 制限が強すぎるため, わずかしか肯定的な結果は得られていなかった.その後, Yokomori(1995)がPittの定義中の条件を緩和した定義を提案し, 正則言語の部分クラスであるstrictly regular languageのクラスに対して多項式時間極限同定可能であることを示した.本稿では, strictly regular languageのクラスとは比較不能な関係にある, ある正則言語の部分クラスを提唱し, このYokomoriの定義において多項式時間極限同定可能であることを示す. |
| 抄録(英) | We show s new result on identification in the limit of regular languages in some subclass. Pitt defined polynomial time identification in the limit in 1989, but it is too restrictive, then only few positive results were obtained in his definition. Later, Yokomori presented another definition of Pitt's in 1995, and showed identifiability in the limit of regular languages in some subclass in his new definition.In this note, we introduce a new subclass of regular languages, and show that the language in this subclass is identifiable in the limit from positive data in the sense of Yokomori. |
| キーワード(和) | 帰納推論 / 正の例からの学習 / 有限オートマトン / 正則言語 |
| キーワード(英) | inductive inference / identification from positive data / finite automaton / regular language |
| 資料番号 | COMP2001-28 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/7/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 正則言語のある部分クラスに対する正の例からの多項式時間極限同定 |
| サブタイトル（和） | |
| タイトル（英） | Polynomial Time Identification in the Limit of Regular Languages in Some Subclass |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 帰納推論 / inductive inference |
| キーワード(2)（和/英） | 正の例からの学習 / identification from positive data |
| キーワード(3)（和/英） | 有限オートマトン / finite automaton |
| キーワード(4)（和/英） | 正則言語 / regular language |
| 第 1 著者 氏名（和/英） | 吉成 智和 / Tomokazu YOSHINARI |
| 第 1 著者 所属（和/英） | 電気通信大学大学院 電気通信学研究科 Graduate School of Electro-Communications The University of Electro-Communications |
| 第 2 著者 氏名（和/英） | 富田 悦次 / Etsuji TOMITA |
| 第 2 著者 所属（和/英） | 電気通信大学大学院 電気通信学研究科 Graduate School of Electro-Communications The University of Electro-Communications |
| 第 3 著者 氏名（和/英） | 若月 光夫 / Mitsuo WAKATSUKI |
| 第 3 著者 所属（和/英） | 電気通信大学大学院 電気通信学研究科 Graduate School of Electro-Communications The University of Electro-Communications |
| 発表年月日 | 2001/7/9 |
| 資料番号 | COMP2001-28 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 184 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |