Parallel Computation of Reachable Dead States in a Free-Choice Petri Net

摘要

Free-choice Petri nets are a prominent tool for modeling and analyzingcommunication protocols, multiprocessor systems, parallel programs, flexible manufacturing systems and workflow scripts. Unfortunately, analysis is often hampered by the state-explosion phenomenon. Even for free-choice petri nets, the reachability problem is known to be EXSPACE-hard. In this paper the authors discuss a technique for the parallel computation of the reachable dead states. This technique is based on the partitioning of tokens instead of the Petri net. (Copyright (c) 1996 Eindhoven University of Technology.)