For the most recent entries see the Petri Nets Newsletter.

A Unified Approach for Reasoning about Conflict-Free Petri Nets.

Yen, Hsu-Chun; Wand, B.-Y.; Yang, M.-S.

In: Ajmone Marsan, M.: Lecture Notes in Computer Science, Vol. 691; Application and Theory of Petri Nets 1993, Proceedings 14th International Conference, Chicago, Illinois, USA, pages 513-531. Springer-Verlag, 1993.

Abstract: The aim of this paper is to develop a unified approach for deriving complexity results for problems concerning conflict-free Petri nets. To do so, we first define a class of formulas for paths in Petri nets. We then show that answering the satisfiability problem for conflict-free Petri nets is tantamount to solving a system of linear inequalities (which is known to be in P). Since a wide spectrum of Petri net problems (including various fairness-related problems) can be reduced to the satisfiability problem in a straightforward manner, our approach offers an umbrella under which many Petri net problems for conflict-free Petri nets can be shown to be solvable in polynomial time. As a side-product, our analysis provides evidence as to why detecting unboundedness for conflict-free Petri nets is easier (provided P is not equal to NP) than for normal and sinkless Petri nets (which are two classes that properly contain that of conflict-free Petri nets).


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography