Exploiting partial symmetries for Markov chain aggregation

L. Capra; C. Dutheillet; G. Franceschinis; J. M. Ilie

doi:10.1016/S1571-0661(05)80750-9

Exploiting partial symmetries for Markov chain aggregation

L. Capra
, C. Dutheillet
, G. Franceschinis
, J. M. Ilie

Department of Science and Technological Innovation

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English
Pages (from-to)	231-257
Number of pages	27
Journal	Electronic Notes in Theoretical Computer Science
Volume	39
Issue number	3
DOIs	https://doi.org/10.1016/S1571-0661(05)80750-9
Publication status	Published - 2000
Event	MTCS 2000 (Satellite Workshop of CONCUR 2000) - State College, United States Duration: 26 Aug 2000 → 26 Aug 2000

Keywords

Extended Symbolic Reachability Graph
High-level Petri Nets
Lumpable Markov Chains
Symmetries

Access to Document

10.1016/S1571-0661(05)80750-9

Cite this

@article{befd88ced1274b8d8744f59dd31679c7,

title = "Exploiting partial symmetries for Markov chain aggregation",

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.",

keywords = "Extended Symbolic Reachability Graph, High-level Petri Nets, Lumpable Markov Chains, Symmetries",

author = "L. Capra and C. Dutheillet and G. Franceschinis and Ilie, \{J. M.\}",

note = "Funding Information: 1 This work was partially supported by the Italian MURST 60\% and by the EEC project n. 28620 TIRAN.; MTCS 2000 (Satellite Workshop of CONCUR 2000) ; Conference date: 26-08-2000 Through 26-08-2000",

year = "2000",

doi = "10.1016/S1571-0661(05)80750-9",

language = "English",

volume = "39",

pages = "231--257",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier B.V.",

number = "3",

}

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 - https://www.scopus.com/pages/publications/2942587701

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 -

Exploiting partial symmetries for Markov chain aggregation

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this