The Existence Of Dependent Siphons Based On Structure Analysis Of Petri Nets

This thesis is devoted to the character of Linear S3PR (L-S3PR) net, a subnet of Petri nets, and analyzes the necessity of the existence of dependent siphons.Siphon is one characteristic of a net, as its subclass, strict minimal siphon (SMS) can represent its liveness more. It is just the unreasonable resource allocation that leads to a deadlock. The System of Simple Sequential Processes with Resource (S3PR) can model for a big class of Flexible Manufactory System (FMS), arouse people abroad attention due to its favorable characteristic. In its subclass, L-S3PR, the circular wait turns to be sufficient and necessary condition of deadlock.The strongly connected subnet which is composed of resource nodes and their transitions were abstracted and called as resource directed graph. The circular wait of resource expresses itself by the occurrence of circle in resource directed graph, named as resource circuit. After study, the author discovers that SMSs correspond to resource circles one by one in an L-S3PR net.In a S3PR net, it is exactly the existence of complementary set that induces the SMS to be emptied during a net's evolution. The SMSs were divided into elementary, strongly and weakly dependent siphons according their matrix character of T-characteristic vector. Every complementary set of a dependent siphon would be linearly expressed by the complementary sets of its elementary siphons, and the combined relation could be equated entirely with that between T-characteristic vector of dependent and its elementary siphons. Circle matrix is the algebraic description of all the resource circles in a directed graph, and equivalence reciprocally to that one of complementary set and T-characteristic vector. And then, the relations between resource circles can be used to describe the required structure condition expediently and intuitively when a dependent siphon inevitably exists.By analyzing plenty of net structures which exist dependent siphon and their resource directed graph, the characteristic of directed graph that inevitable exists dependent siphon was summarized and proved. The existence of dependent siphon could be ensured through resource directed graph, this supply a concise and quick method to judge the property of a net.