Abstract
An algorithm is presented for the general Petri net reachability problem. It is based on a generalization of the basic reachability tree construction which is made symmetric with respect to the initial and final marking. Sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by Presburger expressions. The approximation algorithm is iterated until a sufficient criterion for reachability is satisfied. The exact computational complexity of our algorithm is an open problem.
Keywords
ReachabilityPetri netReachability problemIterated functionGeneralizationMathematicsAlgorithmTree (set theory)AutomatonStochastic Petri netComputational complexity theoryNet (polyhedron)Discrete mathematicsComputer scienceTheoretical computer scienceCombinatorics
Related Publications
Stochastic Petri net representation of discrete event simulations
In the context of discrete event simulation, the marking of a stochastic Petri net (SPN) corresponds to the state of the underlying stochastic process of the simulation and the ...
A partial solution to the reachability-problem for vector-addition systems
With geometrical techniques we hope to bring new insight into the reachability problem for vector-addition systems, which is pertaining in many areas in computer science theory ...
IQPNNI: Moving Fast Through Tree Space and Stopping in Time
An efficient tree reconstruction method (IQPNNI) is introduced to reconstruct a phylogenetic tree based on DNA or amino acid sequence data. Our approach combines various fast al...
New spectral methods for ratio cut partitioning and clustering
Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approxi...
The order of sequence alignment can bias the selection of tree topology.
Sequential pairwise alignment of multiple sequences is a widely used procedure (Kruskal 1983 ).It is useful and generally successful when sequences within a set differ by relati...
Publication Info
- Year
- 1984
- Type
- article
- Volume
- 13
- Issue
- 3
- Pages
- 441-460
- Citations
- 453
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
453
OpenAlex
Cite This
Ernst Mayr
(1984).
An Algorithm for the General Petri Net Reachability Problem.
SIAM Journal on Computing
, 13
(3)
, 441-460.
https://doi.org/10.1137/0213029
Identifiers
- DOI
- 10.1137/0213029