TY - JOUR
T1 - Symbolic state-space exploration and numerical analysis of state-sharing composed models
AU - Derisavi, Salem
AU - Kemper, Peter
AU - Sanders, William H.
N1 - Funding Information:
Contract/grant sponsor: This material is based upon work supported by the National Science Foundation under Grant Nos. CCR-00-86096 and INT-0233490 and by DFG, SFB 559, and the DAAD/NSF exchange project (PPP USA) No. D/0247256. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors. ∗ Corresponding author.
PY - 2004/7/15
Y1 - 2004/7/15
N2 - The complexity of stochastic models of real-world systems is usually managed by abstracting details and structuring models in a hierarchical manner. Systems are often built by replicating and joining subsystems, making possible the creation of a model structure that yields lumpable state spaces. This fact has been exploited to facilitate model-based numerical analysis. Likewise, recent results on model construction suggest that decision diagrams can be used to compactly represent large continuous time Markov chains (CTMCs). In this paper, we present an approach that combines and extends these two approaches. In particular, we propose methods that apply to hierarchically structured models with hierarchies based on sharing state variables. The hierarchy is constructed in a way that exposes structural symmetries in the constructed model, thus facilitating lumping. In addition, the methods allow one to derive a symbolic representation of the associated CTMC directly from the given model without the need to compute and store the overall state space or CTMC explicitly. The resulting representation of a generator matrix allows the analysis of large CTMCs in lumped form. The efficiency of the approach is demonstrated with the help of two example models.
AB - The complexity of stochastic models of real-world systems is usually managed by abstracting details and structuring models in a hierarchical manner. Systems are often built by replicating and joining subsystems, making possible the creation of a model structure that yields lumpable state spaces. This fact has been exploited to facilitate model-based numerical analysis. Likewise, recent results on model construction suggest that decision diagrams can be used to compactly represent large continuous time Markov chains (CTMCs). In this paper, we present an approach that combines and extends these two approaches. In particular, we propose methods that apply to hierarchically structured models with hierarchies based on sharing state variables. The hierarchy is constructed in a way that exposes structural symmetries in the constructed model, thus facilitating lumping. In addition, the methods allow one to derive a symbolic representation of the associated CTMC directly from the given model without the need to compute and store the overall state space or CTMC explicitly. The resulting representation of a generator matrix allows the analysis of large CTMCs in lumped form. The efficiency of the approach is demonstrated with the help of two example models.
KW - Matrix diagrams
KW - Multi-valued decision diagrams
KW - Numerical analysis
KW - Symbolic state-space exploration
UR - http://www.scopus.com/inward/record.url?scp=2942620807&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=2942620807&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2004.01.006
DO - 10.1016/j.laa.2004.01.006
M3 - Conference article
AN - SCOPUS:2942620807
SN - 0024-3795
VL - 386
SP - 137
EP - 166
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
IS - 1-3 SUPPL.
T2 - Conference on the Numerical Solution of MC
Y2 - 3 September 2003 through 5 September 2003
ER -