| 講演名 | 2004/3/8 空スタック受理式決定性1カウンタオートマトンのある部分クラスに対する正の例からの多項式時間極眼同定 若月 光夫, 寺口 潔, 富田 悦次, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | スタック記号が1種類だけの決定性プッシユダウンオートマトン(DPDA)を狭義の決定性1カウンタオートマトン(DROCA)と呼ぶ.本稿では,Szilard strict DROCA と呼ぶ,実時間空スタック受理式DROCAの部分クラスを定義し,このクラスがYokomoriの定義による正の例からの多項式時間極眼同定が可能であることを示す.この言語クラスは,正の例からの極限同定が可能な,0-reversible言語のクラスやvery simple言語のクラスとはそれぞれ比較不能の関係にある.この言語クラスの多項式時間極限同定可能性は,その特徴サンプルの要素数がDPDAの記述長の多項式サイズで抑えられることに因っており,very simple言語の特徴サンプルの要素数が文法(またはDPDA)の記述長の多項式サイズで抑えられるか未知であることと対照的である. |
| 抄録(英) | A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). When it accepts by empty stack, it is called strict This article is concerned with a subclass of real-time strict droca's, called Szilard strict droca's, and deals with the problem of identifying the subclass in the limit from positive data. The class of languages accepted by Szilard strict droca's is incomparable to both the classes of zero-reversible languages and of very simple languages. After providing some properties of languages accepted by Szilard strict droca's, we show that the class of Szilard strict droca's is polynomial time identifiable in the limit from positive data in the sense of Yokomori. This identifiability is proved by giving an exact characteristic sample of polynomial size for a language accepted by a Szilard strict droca. The class of very simple languages is also proved to be polynomial time identifiable in the limit from positive data by Yokomori, but it is unknown whether there exists a characteristic sample of polynomial size for any very simple language. |
| キーワード(和) | 多項式時間極限同定 / 正の例 / 実時間決定性1カウンタオートマトン / 特徴サンプル |
| キーワード(英) | polynomial time identification in the limit / positive data / real-time deterministic one-counter automaton / characteristic sample |
| 資料番号 | COMP2003-83 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2004/3/8(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 空スタック受理式決定性1カウンタオートマトンのある部分クラスに対する正の例からの多項式時間極眼同定 |
| サブタイトル（和） | |
| タイトル（英） | Polynomial Time Identification of Strict Deterministic Restricted One-Counter Automata in Some Class from Positive Data |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多項式時間極限同定 / polynomial time identification in the limit |
| キーワード(2)（和/英） | 正の例 / positive data |
| キーワード(3)（和/英） | 実時間決定性1カウンタオートマトン / real-time deterministic one-counter automaton |
| キーワード(4)（和/英） | 特徴サンプル / characteristic sample |
| 第 1 著者 氏名（和/英） | 若月 光夫 / Mitsuo WAKATSUKI |
| 第 1 著者 所属（和/英） | 電気通信大学電気通信学部情報通信工学科 Department of Information and Communication Engineering, Faculty of Electro-Communications, The University of Electro-Communications |
| 第 2 著者 氏名（和/英） | 寺口 潔 / Kiyoshi TERAGUCHI |
| 第 2 著者 所属（和/英） | 電気通信大学電気通信学部情報通信工学科 Department of Information and Communication Engineering, Faculty of Electro-Communications, The University of Electro-Communications |
| 第 3 著者 氏名（和/英） | 富田 悦次 / Etsuji TOMITA |
| 第 3 著者 所属（和/英） | 電気通信大学電気通信学部情報通信工学科 Department of Information and Communication Engineering, Faculty of Electro-Communications, The University of Electro-Communications |
| 発表年月日 | 2004/3/8 |
| 資料番号 | COMP2003-83 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 722 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |