A unified approach for deciding the existence of certain petri net paths
Resource
Information and Computation 96 (1): 119-137
Journal
Information and Computation
Journal Volume
96
Journal Issue
1
Pages
119-137
Date Issued
1992
Date
1992
Author(s)
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 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.
Other Subjects
Automata Theory - Computability and Decidability; EXSPACE Completeness; Satisfiability Problems; Mathematical Techniques
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
05.pdf
Size
1.11 MB
Format
Adobe PDF
Checksum
(MD5):3e2f7a13d79d297823ddc64693bd2b31