Hierarchical structuring of superposed GSPNs

Superposed Generalized Stochastic Petri Nets (SGSPNs) and Stochastic Automa ta Networks (SANs) are formalisms to describe Markovian models as a collect ion of synchronously communicating components. Both formalisms allow a comp act representation of the generator matrix of the Markov chain, which can b e exploited for very space efficient analysis techniques. The main drawback of the approaches is that far many models the compositional description in troduces a large. number of unreachable states, such that the gain due to t he compact representation of the generator matrix is completely lost. This paper proposes a new approach to avoid unreachable states without losing th e possibility to represent the generator matrix in a compact form. The cent ral idea is to introduce a preprocessing step to generate a hierarchical st ructure which defines a block structure of the generator matrix, where ever y block can be represented in a compact form similar to the representation of generator matrices originally proposed for SCSPNs or SANs. The resulting structure includes no unreachable slates, needs only slightly more space t han the compact representation developed for SANs and can still be exploite d in efficient numerical solution techniques. Furthermore, the approach is a very efficient method to generate and represent huge reachability sets an d graphs.