Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12]

¡@

Journal of Information Science and Engineering, Vol. 21 No. 1, pp. 129-152 (January 2005)

Reachability and Firing Sequences of
Homogeneous Synchronized Choice Petri Nets*

Daniel Y. Chao
 Department of Management and Information Science
National Chengchi University
Taipei, 116 Taiwan
E-mail: yaw@mis.nccu.edu.tw

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.

Keywords: petri nets, synchronized choice nets, reachability, liveness, synthesis, verification, inconsistent pair

Full Text (¥þ¤åÀÉ) Retrieve PDF document (200501_07.pdf)

Received April 24, 2003; revised August 14, 2003 & March 8, 2004; accepted June 1, 2004.
Communicated by Hsu-Chun Yen.
* This work was supported by the National Science Council under research grant number NSC 90-2213-E-004-001.