| 講演名 | 2001/9/7 ある種のカウンタに対する正の例からの多項式時間極限同定 寺口 潔, 富田 悦次, 若月 光夫, 菊地 崇普, 奥尾 幸司, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | Pitt(1989)は形式言語の帰納推論において"多項式時間"極限同定を定義した.Yokomori(1991)はその定義の下で, 文脈自由文法の特殊な形式である極単純決定性文法に対して, 正の例から多項式時間極限同定が可能であることを示した.本稿では, 文脈自由言語の部分クラスでかつ極単純決定性言語のクラスとは比較不能な関係にある言語クラスを規定する, ある種の実時間カウンタを定義し, Pittの定義による正の例からの多項式時間極限同定が可能であることを示す. |
| 抄録(英) | Pitt(1989) defined polynomial-time identification in the limit for a class of languages, and Yokomori(1991) showed polynomial-time identifiability in the limit of very simple grammars from positive data in Pitt's definition. In this note, we are concerned with certain real-time counters, whose class of accepting languages is incomparable to that of very simple languages, and we show that they are polynomial-time identifiable in the limit from positive data in the sense of Pitt. |
| キーワード(和) | 形式言語 / 帰納推論 / 実時間カウンタ / 正例 / 多項式時間極限同定 |
| キーワード(英) | formal language / inductive inference / real-time counters / positive data / polynomial-time identification in the limit |
| 資料番号 | COMP2001-30 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/9/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ある種のカウンタに対する正の例からの多項式時間極限同定 |
| サブタイトル（和） | |
| タイトル（英） | Polynomial-Time Identification in the Limit of Counters in Some Class from Positive Data |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 形式言語 / formal language |
| キーワード(2)（和/英） | 帰納推論 / inductive inference |
| キーワード(3)（和/英） | 実時間カウンタ / real-time counters |
| キーワード(4)（和/英） | 正例 / positive data |
| キーワード(5)（和/英） | 多項式時間極限同定 / polynomial-time identification in the limit |
| 第 1 著者 氏名（和/英） | 寺口 潔 / Kiyoshi TERAGUCHI |
| 第 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 |
| 第 4 著者 氏名（和/英） | 菊地 崇普 / Takahiro KIKUCHI |
| 第 4 著者 所属（和/英） | 電気通信大学大学院電気通信学研究科電子情報学専攻 Graduate School of Electro-Communications The University of Electro-Communications |
| 第 5 著者 氏名（和/英） | 奥尾 幸司 / Koji OKUO |
| 第 5 著者 所属（和/英） | 電気通信大学大学院電気通信学研究科電子情報学専攻 Graduate School of Electro-Communications The University of Electro-Communications |
| 発表年月日 | 2001/9/7 |
| 資料番号 | COMP2001-30 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 307 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |