Yen, Hsu-ChunHsu-ChunYen2009-03-042018-07-062009-03-042018-07-061992https://www.scopus.com/inward/record.uri?eid=2-s2.0-0026685401&doi=10.1016%2f0890-5401%2892%2990059-O&partnerID=40&md5=861f659c357ca32d5b630105a923d64fIn 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 is EXPSPACE complete. Since a wide range of Petri net problems can be reduced to the satisfiability problem in a straightforward manner, our approach offers an umbrella under which many Petri net Problems can be shown to be solvable in EXPSPACE. © 1992.application/pdf1166138 bytesapplication/pdfen-USAutomata Theory - Computability and Decidability; EXSPACE Completeness; Satisfiability Problems; Mathematical Techniquesjournal article10.1016/0890-5401(92)90059-O2-s2.0-0026685401http://ntur.lib.ntu.edu.tw/bitstream/246246/142307/1/05.pdf