On the Efficient Construction of the Tangible Reachability Graph of Generalized Stochastic Petri Nets

The explosion of the number of vanishing markings in GSPN models with a reasonably small number of tangible states is an important practical problem that may prevent the solution of relatively simple models. A new definition of GSPN in which structural properties of the underlying PN are used to guide the specification of random switches at the net level, can be usefully exploited to partition the immediate transitions of a model into extended conflict sets that may be treated independently of each other. The parallelism and the independence inherent in this approach are exploited to devise efficient algorithms for the construction of the state space of the Markov model associated with a GSPN in which subnets of immediate transitions are identified and multiple firing of immediate transitions is performed.