Presentation | 1994/11/17 NECESSARY AND SUFFICIENT CONDITION FOR REACHABILITY OF EXTENDED MARKED GRAPHS Kohkichi TSUJI, Tadao MURATA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | In order to check the reachability of Petri Nets (PNs), it is important to derive the solutions of its state equation because the existence of the solutions is a necessary condition for reachability. In Extended Marked Graphs (EMGs), the algorithm with O(nm) which derives all non-negative solutions of its state equation has been derived, where an EMG is in a subclass of PNs and it can be looked upon as a Marked Graph (MG) with a special type of arcs called the controlling arc. Note that "n" is the number of places and "m" is the number of transitions. In this paper, first, we derive the sufficient condtion that each transition can fire at least one time by using the solutions of its state equation for an EMG. Furthermore, by using these properties, we derive the necessary and sufficient condtion for reachability of EMGs. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Petri net / marked graph / extended marked graph / state equation / reachability |
Paper # | CAS94-70,CST94-30 |
Date of Issue |
Conference Information | |
Committee | CST |
---|---|
Conference Date | 1994/11/17(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) | NECESSARY AND SUFFICIENT CONDITION FOR REACHABILITY OF EXTENDED MARKED GRAPHS |
Sub Title (in English) | |
Keyword(1) | Petri net |
Keyword(2) | marked graph |
Keyword(3) | extended marked graph |
Keyword(4) | state equation |
Keyword(5) | reachability |
1st Author's Name | Kohkichi TSUJI |
1st Author's Affiliation | Faculty of Engineering Fukui University() |
2nd Author's Name | Tadao MURATA |
2nd Author's Affiliation | Department of EECS University of Illinois at Chicago |
Date | 1994/11/17 |
Paper # | CAS94-70,CST94-30 |
Volume (vol) | vol.94 |
Number (no) | 333 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |