The technique presented in this paper allows the automatic construction of a lumped Markov chain for almost symmetrical Stochastic Well-formed Net (SWN) models. The starting point is the Extended Symbolic Reachability Graph (ESRG), which is a reduced representation of a SWN model reachability graph (RG), based on the aggregation of states into classes. These classes may be used as aggregates for lumping the Continuous Time Markov Chain (CTMC) isomorphic to the model RG: however it is not always true that the lumpability condition is verified by this partition of states. In the paper we propose an algorithm that progressively refines the ESRG classes until a lumped Markov chain is obtained.
Exploiting partial symmetries for Markov chain aggregation / L. Capra, C. Dutheillet, G. Franceschinis, J.M. Ilie. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - 39:3(2000), pp. 231-257. ((Intervento presentato al 11. convegno MTCS (Satellite Workshop of CONCUR) tenutosi a State College, USA nel 2000 [10.1016/S1571-0661(05)80750-9].
Exploiting partial symmetries for Markov chain aggregation
L. CapraPrimo
;
2000
Abstract
The technique presented in this paper allows the automatic construction of a lumped Markov chain for almost symmetrical Stochastic Well-formed Net (SWN) models. The starting point is the Extended Symbolic Reachability Graph (ESRG), which is a reduced representation of a SWN model reachability graph (RG), based on the aggregation of states into classes. These classes may be used as aggregates for lumping the Continuous Time Markov Chain (CTMC) isomorphic to the model RG: however it is not always true that the lumpability condition is verified by this partition of states. In the paper we propose an algorithm that progressively refines the ESRG classes until a lumped Markov chain is obtained.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
