Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.15 No.4, pp.543-568 (July 1999)
Petri Net Synthesis and Synchronization
Using Knitting Technique

Daniel Y. Chao
Department of Management and Information Science
National Chengchi University
Taipei, Taiwan 116, R.O.C.

Petri net (PN) synthesis can avoid the state exploration problem, which is of exponential complexity, by guaranteeing the correctness in the Petri net while incrementally expanding the net. The conventional Petri net synthesis approaches, in general, suffer the drawback of only being able to synthesize a few classes of nets. However, the knitting technique, originally proposed by Chao [1-4], can synthesize Petri nets beyond assymetric-choice nets. In addition, one major advantage of the knitting technique is that the resultant Petri net is guaranteed to be live, bounded, and reversible ?the well-behaved properties. Therefore, the cumbersome reanalysis and modification procedures that are inevitable for the conventional Petri net synthesis methods can be avoided. Most current synthesis techniques cannot handle systems with shared resources. Zhou et al. [5] presented the conditions for a PN containing Sequential Mutual Exclusion (SME) to be live, bounded, and deadlock-free. The major motivation of this work is to generalize Zho et al.s pioneering work [5] and to extend the knitting technique to construction of classes of PNs that involve synchronization and shared resources according to the synthesis rules. In addition, the knitting technique developed prior to this work concentrated on the structural relationships among the pseudo-processes only and was not related to the marking. This paper is the first work to consider marking in the PN synthesis with the knitting technique.

Keywords: Petri net, knitting technique, synchronization, deadlock, SME, liveness, boundedness, shared resource

Full Text () Retrieve PDF document (199907_05.pdf : 236,300 bytes)

Received December 2, 1996; accepted September 26, 1997.
Communicated by Shing-Tsaan Huang.


  1. Y. Yaw, (now D.Y. Chao), "Analysis and synthesis of distributed systems and protocols," Ph.D. Dissertation, Dept. of EECS, U.C. Berkeley, 1987.
  2. F.L. Foun, "The algorithm of a synthesis technique for concurrent systems," IEEE International Workshop on Petri Nets and Performance Models, 1989, pp. 266-276.
  3. D.Y. Chao and D.T. Wang, "Two theoretical and practical aspects of knitting technique - Invariants and a new class of Petri net," IEEE Transactions on Systems, Man and Cybernatics, Vol. 27, No. 7, 1997, pp. 926-9373.
  4. D.Y. Chao, "Linear algebra based verification of well-behaved properties and P-invariants of Petri nets synthesized using knitting technique," Management Information System Review, Vol. 5, 1995, pp. 27-48.
  5. M.C. Zhou and F. DiCesare, "Parallel and sequential mutual exclusions for Petri net modeling for manufacturing systems with shared resources," IEEE Transactions on Robotics and Automation, Vol. 7, No. 4, 1991, pp. 515-527.