Title: Hierarchical Reachability Graph Generation for Petri Nets

Author: Peter Buchholz and Peter Kemper

Abstract: 
Reachability analysis is the most general approach to analyze Petri
nets. Due to state space explosion, generation of the reachability set
and reachability graph becomes intractable even for moderately sized
nets with the known approaches. This paper presents a new method to
generate and represent the reachability set and reachability graph of
large Petri nets in a compositional and hierarchical way. The
representation is related to previously known Kronecker based
representations and it contains the complete information about
reachable markings and possible transitions. The central idea of the
new technique is a divide and conquer approach. Based on net-level
results, nets are decomposed and reachability graphs for parts are
generated and combined. The whole approach can be realized in a
completely automated way and has been integrated in a Petri Net based
analysis tool.

Published in: 
Universit�ät Dortmund, Fachbereich Informatik, Forschungsbericht Nr. 660, 1997