Presentation | 2018-11-12 Stability Subnet Detection of Petri Net by Circuit Flow-Matrix Transformation Yojiro Harie, Katsumi Wasaki, |
---|---|
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 describes distributed systems. For dynamic analysis of Petri net, it is necessary to generate behaviors from the initial state as state space. However, there is a problem that exploring an large state space incurs significant memory and time costs. In the analysis method for large scale net, graph partitioning and contraction are proposed. The S-invariant is a property which means the total sum of weighted tokens in Petri net places is constant. Although invariants are obtained from state equations, the total number is generally unknown. Therefore, for the easy retrieval of partial net of stable behavior is useful for property verification and state generation. In this research, in order to perform partial net partitioning of Petri nets, we convert to the weighted directed graph "Flow-net" with the ratio of increase / decrease of tokens between places as a connection. We define "Stability" as a criterion for the constant number of tokens on the flow net. It reduces to a maximizing problem that evaluates based on Stability for a given partition. Graph partitioning can be obtained by a set of family of node sets, but for the efficiency we extract only connected components. In this paper, we show that the detection of Stability subnet of the liveness Free Choice net is enabled restricting target net to cycle net. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Petri Net / Flow-Matrix Transformation / Graph Partitioning / Stability Subnet / Stability |
Paper # | CAS2018-64,MSS2018-40 |
Date of Issue | 2018-11-05 (CAS, MSS) |
Conference Information | |
Committee | MSS / CAS / IPSJ-AL |
---|---|
Conference Date | 2018/11/12(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Morikazu Nakamura(Univ. of Ryukyus) / Hideaki Okazaki(Shonan Inst. of Tech.) |
Vice Chair | Shigemasa Takai(Osaka Univ.) / Taizo Yamawaki(Hitachi) |
Secretary | Shigemasa Takai(Toshiba) / Taizo Yamawaki(Osaka Univ.) / (Shonan Inst. of Tech.) |
Assistant | Hideki Kinjo(Okinawa Univ.) / Motoi Yamaguchi(Renesas Electronics) |
Paper Information | |
Registration To | Technical Committee on Mathematical Systems Science and its applications / Technical Committee on Circuits and Systems / Special Interest Group on Algorithms |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Stability Subnet Detection of Petri Net by Circuit Flow-Matrix Transformation |
Sub Title (in English) | |
Keyword(1) | Petri Net |
Keyword(2) | Flow-Matrix Transformation |
Keyword(3) | Graph Partitioning |
Keyword(4) | Stability Subnet |
Keyword(5) | Stability |
1st Author's Name | Yojiro Harie |
1st Author's Affiliation | Shinshu University(Shinshu Univ.) |
2nd Author's Name | Katsumi Wasaki |
2nd Author's Affiliation | Shinshu University(Shinshu Univ.) |
Date | 2018-11-12 |
Paper # | CAS2018-64,MSS2018-40 |
Volume (vol) | vol.118 |
Number (no) | CAS-295,MSS-296 |
Page | pp.pp.37-42(CAS), pp.37-42(MSS), |
#Pages | 6 |
Date of Issue | 2018-11-05 (CAS, MSS) |