| Presentation | 1997/10/31 Minimal Realizations of Deterministic Finite Automata using Ho-Kalman's Algorithm Koji WATANABE, Takeo IKAI, Kunio FUKUNAGA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Regarding finite Automata (FAs) as discrete time dynamical systems, state space models of FAs can be constructed over B(={0, 1}). As a result, the concepts such as reachability, observability etc. can be defined on state space models of FAs as well as linear dynamical systems over the real field R. In this paper, we propose a minimal realization method of deterministic FAs using Ho-Kalman's algorithm from Hankel matrices constructed by input-output responses of FAs. Since state space models of FAs are bilinear over B and Ho-Kalman's algorithm is, on the other hand, one for linear systems over R, we add some extensions to their algorithm. Furthermore, we derive a minimal partial realization algorithm from finite sub-Hankel matrices. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | finite automata / state space model / Hankel matrix / minimal realization / Ho-Kalman's algorithm |
| Paper # | COMP97-52 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1997/10/31(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Minimal Realizations of Deterministic Finite Automata using Ho-Kalman's Algorithm |
| Sub Title (in English) | |
| Keyword(1) | finite automata |
| Keyword(2) | state space model |
| Keyword(3) | Hankel matrix |
| Keyword(4) | minimal realization |
| Keyword(5) | Ho-Kalman's algorithm |
| 1st Author's Name | Koji WATANABE |
| 1st Author's Affiliation | Faculty of Engineering, Osaka Prefecture University() |
| 2nd Author's Name | Takeo IKAI |
| 2nd Author's Affiliation | Faculty of Engineering, Osaka Prefecture University |
| 3rd Author's Name | Kunio FUKUNAGA |
| 3rd Author's Affiliation | Faculty of Engineering, Osaka Prefecture University |
| Date | 1997/10/31 |
| Paper # | COMP97-52 |
| Volume (vol) | vol.97 |
| Number (no) | 356 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |