| 講演名 | 1996/1/26 非決定性オートマトンの状態モデル表現 猪飼 武夫, 塩見 なぎさ, 福永 邦雄, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本報告では, 記号列を単位ベクトルにより表現する符号化を導入して時点表示を状態ベクトルとして表現し, さらにテープ領域を限定することにより, 非決定性チューリング機械(NTM)の有限状態の領域限定状態モデルを構成している. この状態モデル上で可到達性およぴ可観測性を定義し, TMにおける受理および拒否などとの関係を明らかにし, さらに共通集合や補集合などを受理するモデルの構成法を導いている. |
| 抄録(英) | In this paper, introducing a coding method of a string which represent it as a unite vector, a instantaneous description of Turing machine(TM) can be represented as a state vector. By bounding the TM tape space, we construct space bounded state space models having finite states for nondeterministic TM's. Reachability and observability are defined over these state models and shown relationship to the acceptance and reject in TM. Moreover we derive a method for constructing state models which accept a union, intersection and complement of languages. |
| キーワード(和) | 非決定性チューリング機械 / 状態空間モデル / 記号列の符号化 / 可到達性 / 共通集合 / 補集合 |
| キーワード(英) | nondeterministic Turing machine / state space model / coding of string / reachability / intersection / complement |
| 資料番号 | COMP95-84 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1996/1/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非決定性オートマトンの状態モデル表現 |
| サブタイトル（和） | |
| タイトル（英） | State Model Representations of Nondeterministic Automata |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 非決定性チューリング機械 / nondeterministic Turing machine |
| キーワード(2)（和/英） | 状態空間モデル / state space model |
| キーワード(3)（和/英） | 記号列の符号化 / coding of string |
| キーワード(4)（和/英） | 可到達性 / reachability |
| キーワード(5)（和/英） | 共通集合 / intersection |
| キーワード(6)（和/英） | 補集合 / complement |
| 第 1 著者 氏名（和/英） | 猪飼 武夫 / Takeo IKAI |
| 第 1 著者 所属（和/英） | 大阪府立大学工学部 Faculty of Engineering, Osaka Prefecture University |
| 第 2 著者 氏名（和/英） | 塩見 なぎさ / Nagisa SHIOMI |
| 第 2 著者 所属（和/英） | 大阪府立大学工学部 Faculty of Engineering, Osaka Prefecture University |
| 第 3 著者 氏名（和/英） | 福永 邦雄 / Kunio FUKUNAGA |
| 第 3 著者 所属（和/英） | 大阪府立大学工学部 Faculty of Engineering, Osaka Prefecture University |
| 発表年月日 | 1996/1/26 |
| 資料番号 | COMP95-84 |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 498 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |