| Presentation | 2000/1/18 Improved Implementation of the Fourier-Motzkin Method for Computing Petri Net Invariants Masahiro Yamauchi, Keisuke Nishiuchi, Toshimasa Watanabe, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | An invariant of a Petri net N=(P, T, E)is a |T|-dimensional vector X(a T-invariant)with A・X=0(zero vector)or a |P|-dimensional vector Y(a P-invariant)with Y^t・A=0 for the place-transition incidence matrix A of N. The Fourier-Motzkin(FM)method is well-known for computing all such nonnegative integer invariants. This method, however, has a critical deficiency: computation may be interrupted and no output is given because of memory overflow in storing intermediary vectors which are candidates for invariants. In order to overcome this deficiency, STFM has been proposed: it reduces the computation to smaller subnets based on siphons and tarps. The paper considers another direction of improvement: finding appropriate order of computation or deleting useless vectors so as not to increase the number of candidate vectors. Several ideas for such improvement are incorporated in both FM method and STAF. Their effects are experimentally evaluated, and some of them show great improvement. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Petri net invariants / minimal supports / siphons / traps / the Fourier-Motzkin metod |
| Paper # | CST99-56 |
| Date of Issue |
| Conference Information | |
| Committee | CST |
|---|---|
| Conference Date | 2000/1/18(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 | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Improved Implementation of the Fourier-Motzkin Method for Computing Petri Net Invariants |
| Sub Title (in English) | |
| Keyword(1) | Petri net invariants |
| Keyword(2) | minimal supports |
| Keyword(3) | siphons |
| Keyword(4) | traps |
| Keyword(5) | the Fourier-Motzkin metod |
| 1st Author's Name | Masahiro Yamauchi |
| 1st Author's Affiliation | Graduate School of Engineering, Hiroshima University() |
| 2nd Author's Name | Keisuke Nishiuchi |
| 2nd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 3rd Author's Name | Toshimasa Watanabe |
| 3rd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| Date | 2000/1/18 |
| Paper # | CST99-56 |
| Volume (vol) | vol.99 |
| Number (no) | 539 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |