Ten Years of Saturation: A Petri Net Perspective

摘要

Due to their appealing conceptual simplicity and availability of computer tools for their analysis, Petri nets are widely used to model discrete-event systems in many areas of engineering. However, the computational resources required to carry out the analysis of a Petri net model are often enormous, hindering their practical impact. In this survey, we consider how symbolic methods based on the use of decision diagrams can greatly increase the size of Petri nets that an ordinary computer can reasonably tackle. In particular, we present this survey from the perspective of the efficient saturation method we proposed a decade ago, and introduce along the way the most appropriate classes of decision diagrams to answer important Petri net questions, from reachability to CTL model checking and counterexample generation, from p-semiflow computation to the solution of timed or Markovian nets.