| 講演名 | 1997/10/31 決定性有限オートマトンの正準分解とそのアルゴリズム 古澤 和久, 猪飼 武夫, 福永 邦雄, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 有限オートマトン (FA) を離散時間動的システムと捉え、状態をB(={0, 1}) 上ベクトルにより表現し、状態推移行列を導入することにより、FAのプール半環B上で状態空間モデルが得られる。本報告ではまず、この状態空間モデルにおける可到達性、可観測性および可識別性に基づきFAにおけるKalmanの正準分解を定義し、決定性FA (DFA) の任意の状態空間モデルが与えられたとき、正準分解により最小DFAが求められることを示す。さらに双対FAの状態ベクトルに基づいた新たな最小化アルゴリズムを導出すると共に、既存のDFAの最小化法が統一的に取り扱えることを示す。 |
| 抄録(英) | Regarding finite automata (FAs) as discrete time dynamical systems, state space models of FAs over Boolean semiring B can be obtained from the expression of states by vectors over B(={0, 1}) and the introduction of state transition matrices. In this paper, we define Kalman's canonical decomposition for FAs based on reachability, observability and distinguishability over state space models. For given arbitrary state space models of deterministic FAs (DFAs), we next show that we can construct the reduced DFA based on canonical decomposition. Moreover we derive a new minimal realization algorithm based on state vectors of dual FA, and we show that we can uniformly treat existing minimization algorithms of DFAs. |
| キーワード(和) | 有限オートマトン / 状態空間モデル / Kalmanの正準分解 / 識別可能性 / 状態最小化アルゴリズム |
| キーワード(英) | finite automata / state space model / Kalman's canonical decomposition / distinguishability / state minimization algorithm |
| 資料番号 | COMP97-51 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1997/10/31(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 決定性有限オートマトンの正準分解とそのアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Canonical Decomposition and Its Algorithms of Deterministic Finite Automata |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 有限オートマトン / finite automata |
| キーワード(2)（和/英） | 状態空間モデル / state space model |
| キーワード(3)（和/英） | Kalmanの正準分解 / Kalman's canonical decomposition |
| キーワード(4)（和/英） | 識別可能性 / distinguishability |
| キーワード(5)（和/英） | 状態最小化アルゴリズム / state minimization algorithm |
| 第 1 著者 氏名（和/英） | 古澤 和久 / Kazuhisa FURUSAWA |
| 第 1 著者 所属（和/英） | 大阪府立大学工学部 Faculty of Engineering, Osaka Prefecture University |
| 第 2 著者 氏名（和/英） | 猪飼 武夫 / Takeo IKAI |
| 第 2 著者 所属（和/英） | 大阪府立大学工学部 Faculty of Engineering, Osaka Prefecture University |
| 第 3 著者 氏名（和/英） | 福永 邦雄 / Kunio FUKUNAGA |
| 第 3 著者 所属（和/英） | 大阪府立大学工学部 Faculty of Engineering, Osaka Prefecture University |
| 発表年月日 | 1997/10/31 |
| 資料番号 | COMP97-51 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 356 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |