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.