Abstract: Elementary siphons are computationally expensive when the size of a Petri net is large. Based on binary search, this paper proposes an efficient algorithm for finding a set of elementary siphons. If the characteristic T-vector matrix of a net is not of row full rank, the matrix is divided into two sub-matrices. This step is repeated until a row full rank sub-matrix is found. The siphons corresponding to the sub-matrix are elementary. Based on these elementary siphons, other elementary siphons can be accordingly found by recursive search in the sub-matrices. This algorithm ensures that the number of times of calculating the ranks of matrices is greatly reduced compared with the traditional sequential search method. For the linear simple sequential process with resources (LS³PR), it is polynomial. Finally, the efficiency is demonstrated by case study.

Key words: Petri net, a system of linear simple sequential process with resources, binary search, elementary siphon