*For the most recent entries see the
Petri Nets Newsletter.*

## Reachability analysis using net unfoldings.

Schröter, C.;
Esparza, J.
In:
Burkhard, H.-D.; Czaja, L.; Skowron, A.; Starke, P.: *Report No. 140: Proceedings of the workhop on Concurrency, Specification and Programming, Oct 9-11, 2000*, pages 255-269.
Berlin: Humboldt-University,
2000.

Abstract:
We study four solutions to the reachability problem for 1-safe Petri nets,
all of them based on the unfolding technique. We define the problem as
follows: given a set of places of the net, determine if some reachable
marking puts a token in all of them. Three of the solutions to the problem
are taken from the literature, while the fourth one is first introduced
here. The new solution shows that the problem can be solved in time O(nk),
where n is the size of the prefix of the unfolding containing all
reachable states, and k is the number of places which should hold a token.
We compare all four solutions on a set of examples, and extract a
recommendation on which algorithms should be used and which ones not.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*