In: Journal of Information Science Engineering, Vol. 15, No. 4, pages 543-568. 1999.
Abstract: Petri net synthesis can avoid the state explosion problem, which is of exponential complexity, by guaranteeing the correctness of 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 can synthesize Petri nets beyond asymmetric choice nets. In addition, one major advantage of knitting technique is that the resultant Petri net is guaranteed to be live, bounded and reversible - the well-behaved properties. Therefore, the cumbersome re-analysis and modification procedures which are inevitable for the conventional Petri net synthesis methods, can be avoided. Most current synthesis techniques cannot handle systems with shared resources. Zhou at al. presented the conditions for a Petri net for a Petri net containing sequential mutual exclusion (SME) to be live, bounded, and deadlock-free. This paper generalizes this previous work and extends the knitting technique to the construction of classes of Petri nets 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 Petri net synthesis with the knitting technique.
Keywords: Petri net synthesis, knitting technique, resource sharing.