| Presentation | 1996/1/26 State Model Representations of Nondeterministic Automata Takeo IKAI, Nagisa SHIOMI, Kunio FUKUNAGA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | nondeterministic Turing machine / state space model / coding of string / reachability / intersection / complement |
| Paper # | COMP95-84 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1996/1/26(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) | State Model Representations of Nondeterministic Automata |
| Sub Title (in English) | |
| Keyword(1) | nondeterministic Turing machine |
| Keyword(2) | state space model |
| Keyword(3) | coding of string |
| Keyword(4) | reachability |
| Keyword(5) | intersection |
| Keyword(6) | complement |
| 1st Author's Name | Takeo IKAI |
| 1st Author's Affiliation | Faculty of Engineering, Osaka Prefecture University() |
| 2nd Author's Name | Nagisa SHIOMI |
| 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 | 1996/1/26 |
| Paper # | COMP95-84 |
| Volume (vol) | vol.95 |
| Number (no) | 498 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |