Symbolic state-space exploration and numerical analysis of state-sharing composed models

Salem Derisavi, Peter Kemper, William H Sanders

Research output: Contribution to journalConference article

Abstract

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.

Original languageEnglish (US)
Pages (from-to)137-166
Number of pages30
JournalLinear Algebra and Its Applications
Volume386
Issue number1-3 SUPPL.
DOIs
StatePublished - Jul 15 2004
EventConference on the Numerical Solution of MC - Urbana-Champaign, IL, United States
Duration: Sep 3 2003Sep 5 2003

    Fingerprint

Keywords

  • Matrix diagrams
  • Multi-valued decision diagrams
  • Numerical analysis
  • Symbolic state-space exploration

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Cite this