Reachability and Firing Sequences of Homogeneous Synchronized Choice Petri Nets

A new local structure called the Second Order Structure (SOS) has been proposed to generate a new class of nets called Synchronized Choice Nets (SNC). SNC covers well-behaved free-choice nets. The reachability problem for Homogeneous SNC (HSNC, a subclass of SNC) is quite simple because reachable markings are linearly additive and can be translated into a structural problem based on the S-Matrix. An algorithm for constructing the S-Matrix has been developed to record the structural relationships among places. Hence, it is no longer a P-Space hard problem, and an algorithm with polynomial time complexity has been developed. Also presented is an algorithm for deriving the shortest firing sequence from one reachable marking to another. How the algorithm can be extended to Inhomogeneous and non-SNC is discussed.

並列關鍵字

petri nets ； synchronized choice nets ； reachability ； liveness ； synthesis ； verification ； inconsistent pair

被引用紀錄

Chang, Y. F. (2016). 國際商務仲裁判斷後審查系統之立法模型 [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU201601682

Hung, H. Y. (2013). 基因序列分段研究 [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2013.00944

國際替代計量

Reachability and Firing Sequences of Homogeneous Synchronized Choice Petri Nets

全文下載

主題瀏覽