Unfolding Based Algorithms for the Reachability Problem

• Autorzy: Esparza J. , Schröter C.
• Języki publikacji: EN

Abstrakty

EN

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 [McM92,Mel98,Hel99], 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.

Słowa kluczowe

EN

Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 47, nr 3,4
• Strony: 231--245
• Opis fizyczny: bibliogr. 12 poz.

Twórcy

autor

Esparza J.

autor

Schröter C.

• Institut für Informatik Technische Universität München,