| Presentation | 1997/1/24 Reachability Criterion for Petri Nets with Known Firing Count Vector Tadashi MATSUMOTO, Yasushi MIYANO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A necessary and sufficient condition on the general Petri net reachability problem is presented by eliminating all spurious solutions among nonnegative integer solutions of state equation. This result is based on the decomposition of a given net and the concepts of "no immature siphon at the original or reduced initial marking" and "no immature trap at the original or reduced end marking" which are both extended from "no token-free siphon at the initial marking" and "no token-free trap at the end marking," respectively, which have been both effectively, explicitly or implicitly, used in the well-known fundamental and simple subclasses. Reach-ability analysis is one of the most fundamental problems among analysis problems of discrete event systems. It has been shown that the reachability problem is decidable although it, takes at least exponential space and time to verify in the general case. The reachability criterion obtained in this paper of course includes, as the special cases, the most wider subclasses with easier decidable and known reachability criteria such as NOT-nets and NOP-nets (both nets are subclasses of free choice nets). |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | General Petri nets / Reachability / State equation / Spurious solutions / Net decomposition / Immature siphons or traps |
| Paper # | CST96-29 |
| Date of Issue |
| Conference Information | |
| Committee | CST |
|---|---|
| Conference Date | 1997/1/24(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 | Concurrent System Technology (CST) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Reachability Criterion for Petri Nets with Known Firing Count Vector |
| Sub Title (in English) | |
| Keyword(1) | General Petri nets |
| Keyword(2) | Reachability |
| Keyword(3) | State equation |
| Keyword(4) | Spurious solutions |
| Keyword(5) | Net decomposition |
| Keyword(6) | Immature siphons or traps |
| 1st Author's Name | Tadashi MATSUMOTO |
| 1st Author's Affiliation | Faculty of Engineering, Fukui University() |
| 2nd Author's Name | Yasushi MIYANO |
| 2nd Author's Affiliation | Faculty of Engineering, Fukui University |
| Date | 1997/1/24 |
| Paper # | CST96-29 |
| Volume (vol) | vol.96 |
| Number (no) | 493 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |