| Presentation | 2011/11/10 On Some Algorithms to Verify Trap Containing Circuit Nets Atsushi OHTA, Kohkichi TSUJI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Petri net is a graphical and mathematical modeling tool for concurrent systems. Analysis of general Petri net requires vast computational cost. There are some subclasses of Petri net with less computational complexity and moderate modeling power. In this report, three subclasses are considered: trap circuit nets (TC), structurally weak persistent nets (SWPN) and trap containing circuit net (TCC). TC net can be verified in polynomial time, which is shown by reducing the problem to linear programming. Verification problems of other two subclasses have been proved to be co-NP complete. This report shows graph theoretic method to verify TC nets. SWPN and TCC nets can be verified by reducing them to satisfiability problems of boolean expression, which are based on the method proposed by Oanea et al. to detect siphon containing no traps. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | concurrent system / Petri net / verification of subclasses / satisfiability problem |
| Paper # | MSS2011-37,CAS2011-68 |
| Date of Issue |
| Conference Information | |
| Committee | MSS |
|---|---|
| Conference Date | 2011/11/10(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 | Mathematical Systems Science and its applications(MSS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On Some Algorithms to Verify Trap Containing Circuit Nets |
| Sub Title (in English) | |
| Keyword(1) | concurrent system |
| Keyword(2) | Petri net |
| Keyword(3) | verification of subclasses |
| Keyword(4) | satisfiability problem |
| 1st Author's Name | Atsushi OHTA |
| 1st Author's Affiliation | School of Information Science and Technology, Aichi Prefectural University() |
| 2nd Author's Name | Kohkichi TSUJI |
| 2nd Author's Affiliation | School of Information Science and Technology, Aichi Prefectural University |
| Date | 2011/11/10 |
| Paper # | MSS2011-37,CAS2011-68 |
| Volume (vol) | vol.111 |
| Number (no) | 294 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |