Graph models for reachability analysis of concurrent programs
Mauro Pezzè, Richard N. Taylor, Michal Young · ACM Transactions on Software Engineering and Methodology · 1995
The problem of analyzing concurrent systems has been investigated by many researchers, and several solutions have been proposed. Among the proposed techniques, reachability analysis—systematic enumeration of reachable states in a finite-state model—is attractive because it is conceptually simple and relatively straightforward to automate and can be used in conjunction with model-checking procedures to check for application-specific as well as general properties. This article shows that the nature of the translation from source code to a modeling formalism is of greater practical importance than the underlying formalism. Features identified as pragmatically important are the representation of internal choice, selection of a dynamic or static matching rule, and the ease of applying reductions. Since combinatorial explosion is the primary impediment to application of reachability analysis, a particular concern in choosing a model is facilitating divide-and-conquer analysis of large programs. Recently, much interest in finite-state verification systems has centered on algebraic theories of concurrency. Algebraic structure can be used to decompose reachability analysis based on a flowgraph model. The semantic equivalence of graph and Petri net-based models suggests that one ought to be able to apply a similar strategy for decomposing Petri nets. We describe how category-theoretic treatments of Petri nets provide a basis for decomposition of Petri net reachability analysis.