In: Jensen, K.: Lecture Notes in Computer Science, Vol. 616; 13th International Conference on Application and Theory of Petri Nets 1992, Sheffield, UK, pages 299-309. Springer-Verlag, June 1992.
Abstract: A new concurrency relation for ordinary Petri nets is introduced. It gives the necessary condition for every pair of places to be marked at some marking. Irreflexiveness of this relation proves to be the sufficient condition of safety of ordinary Petri nets and necessary and sufficient condition of safety of live EFC nets. The complexity of this relation computing has a polynomial upper bound of O(X5), where X is the number of vertices of a net.