Chinese Journal of Computers   Full Text
Title	A Construction Method for the Process Expression of a Petri Net Based on Synchronization Composition
Authors	ZENG Qing-Tian
Address	(College of Information Science and Technology, Shandong University of Science and Technology, Qingdao, Shandong 266510)
Year	2008
Issue	No.3(381—390)
Abstract &   Background	Abstract Process is one of the most useful tools for property analysis of a Petri net, however it is usually difficult to present all the processes of a structure-complex Petri net. Process expression can be used to define the set of all processes for a Petri net. A construction method for the process expression of a Petri net is proposed based on synchronization composition in this paper. The process characteristics of S-Net, a kind of structure-simple Petri net, are analyzed firstly with details, and the approaches to obtain the process expressions of all kinds of S-Nets are obtained. Then, the relationship between the sets of the basic process section during the synchronization composition is analyzed, and the relationship between process expressions is expressed by synchronization shuffle operation of processes. It is proved that a Petri net can be constructed by the synchronization composition of a set of S-Nets, and the process expression of the original Petri net can be obtained based on the process expressions of these S-Nets. keywords Petri net; S-Net; synchronization composition; synchronization shuffle; process; process expression background This work is supported by National Science Foundation of China (60603090, 90718011) and the Excellent Young Scientist Foundation of Shandong Province of China (2006BS01019), supported partially by the Taishan Scholar Program of Shandong Province, and is finished by Petri net group, department of computer science and technology, Shandong University of Science and Technology. To use Petri net for analyzing the properties of the physical systems, several methods have been presented in the net theory. Petri net processes are very convenient for analyzing concurrent phenomena and system properties relating to concurrency. This is one of the advantages of process method compared to other analysis methods of Petri net. However, a process of a Petri net only gives one possible running case for the net system. There are usually many (sometime maybe infinite) cases during a Petri net system running. It is difficult to obtain all the running cases, which brings difficulties for the analysis of Petri nets using their processes. We introduced the concept of process net system of a Petri net, a reconstruction Petri net based on the set of the basic process sections, which can describe the process behaviors of the original system very well. And, the concept of process expression for Petri net is also introduced by our research group. Roughly, any process of a Petri net is really a composition of several basic process sections according to the process expression. We have proved the one-to-one corresponding relation between the transition firing sequences of the process net system and the processes of the original Petri net, and presented a method to obtain the process expression of a Petri net based on its process net system. The method to obtain the process expression of a Petri net especially an unbounded Petri net is usually complex. This paper proposes a new approach to construct the process expression of a Petri net based on synchronization composition. It is proved that a Petri net can be constructed by the synchronization composition of a set of S-Nets which are a kind of structure-simple Petri nets and their processes are easy to express. The process expression of the original Petri net can be obtained based on the synchronization shuffle operation of processes of these S-Nets.