Fourth Asia-Pacific Software Engineering and International Computer Science Conference (APSEC'97 / ICSC'97)
Finite Symbolic Reachability Graphs for High-Level Petri Nets
Clear Water Bay, HONG KONG
December 02-December 05
ISBN: 0-8186-8271-X
The construction of reachability graphs (rg) is one of the most useful techniques to analyze the properties of concurrent systems modeled by Petri nets. Such a graph describes all the possible behaviors of the system, and its construction is straightforward. When high-level Petri nets are under consideration, the size of the graph most often is infinite or large. The reason for this combinatory explosion is twofold: first, we have the explosion due to the interleaving of traces which is usual in models of concurrency; the second explosion results from the token identity since each transition occurrence is characterized by the transition and by the tokens involved in this occurrence. Then, the reachability graph of a bounded net may be infinite, if the domains of tokens are infinite. Symbolic reachability graphs (srg) have been introduced to cope with the latter cause of explosion. By exploiting the symmetries of the net, they are more reduced than the whole reachability graph. This paper introduces a general definition of symbolic reachability graphs. This leads to the introduction of various finite symbolic reachability graphs and to their construction. Two instances of such symbolic rechability graphs are defined. Moreover, a criterion for these two srg to be finite is given together with computation algorithms.
Citation:
Nabil Hameurlain, Christophe Sibertin-Blanc, "Finite Symbolic Reachability Graphs for High-Level Petri Nets," apsec, pp.150, Fourth Asia-Pacific Software Engineering and International Computer Science Conference (APSEC'97 / ICSC'97), 1997