An Effective Algorithm to Find Elementary Siphons in a Class of Petri Nets

As a structural object of Petri nets, siphons play a key role in the development of deadlock prevention policies for resource allocation systems. Elementary siphons are a novel concept in net theory. Based on graph theory, this paper proposes an effective algorithm with polynomial complexity to find a set of elementary siphons for a linear system of simple sequential processes with resources (LS³ PR), a subclass of Petri nets, which can model many flexible manufacturing systems. The algorithm is established through the use of a resource directed graph and complementary sets of strict minimal siphons (SMS) of the net. The upper bound of the number of SMS in such a net is identified. A running example is used to demonstrate the proposed method.