Exploiting Isomorphisms and Special Structures in the Analysis of Markov Regenerative Stochastic Petri Nets

We introduce a refined algorithm for determining the transition probability matrix of the embedded Markov chain underlying a Markov Regenerative Stochastic Petri Net (MRSPN), which continues previous work on improving the efficiency of the numerical solution method for MRSPNs. By observing that the digraph corresponding to the Markov chains subordinated to timed transitions with non-exponentially distributed firing delays of a MRSPN constitute a forest, we show how isomorphisms between its connected components can be exploited in order to reduce the computation time of their transient analysis. Furthermore, special structures for subordinated Markov chains are introduced for which the computational effort of the transient analysis can also be reduced. The computational benefit of the proposed approach is illustrated by four MRSPNs taken from the literature.