In: Information and Computation, Vol. 96, No. 1, pages 119-137. 1992.
Abstract: In this paper, we develop a unified approach for deriving complexity results for a number of Petri net problems. We first define a class of formulas for paths in Petri nets. We then show that the satisfiability problem for our formulas in EXPSPACE complete. Since a wide range of Petri net problems can be reduced to the satisfiablility problem in a straightforward manner, our approach offers an umbrella under which many Petri net problems can be shown to be solvable in EXPSPACE.