TY - JOUR
T1 - Exploiting partial symmetries for Markov chain aggregation
AU - Capra, L.
AU - Dutheillet, C.
AU - Franceschinis, G.
AU - Ilie, J. M.
N1 - Funding Information:
1 This work was partially supported by the Italian MURST 60% and by the EEC project n. 28620 TIRAN.
PY - 2000
Y1 - 2000
N2 - 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.
AB - 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.
KW - Extended Symbolic Reachability Graph
KW - High-level Petri Nets
KW - Lumpable Markov Chains
KW - Symmetries
UR - http://www.scopus.com/inward/record.url?scp=2942587701&partnerID=8YFLogxK
U2 - 10.1016/S1571-0661(05)80750-9
DO - 10.1016/S1571-0661(05)80750-9
M3 - Conference article
SN - 1571-0661
VL - 39
SP - 231
EP - 257
JO - Electronic Notes in Theoretical Computer Science
JF - Electronic Notes in Theoretical Computer Science
IS - 3
T2 - MTCS 2000 (Satellite Workshop of CONCUR 2000)
Y2 - 26 August 2000 through 26 August 2000
ER -