Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains

Tingting Han, Joost P. Katoen, A. Mereacre

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

Abstract

This paper presents a compositional framework for the modeling of interactive continuous-time Markov chains with time-dependent rates, a subclass of communicating piecewise deterministic Markov processes. A poly-time algorithm is presented for computing the coarsest quotient under strong bisimulation for rate functions that are either piecewise uniform or (piecewise) polynomial. Strong as well as weak bisimulation are shown to be congruence relations for the compositional framework, thus allowing component-wise minimization. In addition, a new characterization of transient probabilities in time-inhomogeneous Markov chains with piecewise uniform rates is provided.
Original languageUndefined
Title of host publicationHybrid Systems: Computation and Control (HSCC)
Place of PublicationBerlin
PublisherSpringer
Pages244-258
Number of pages15
ISBN (Print)978-3-540-78928-4
DOIs
Publication statusPublished - Apr 2008
Event11th International Workshop on Hybrid Systems: Computation and Control, HSCC 2008 - St. Louis, United States
Duration: 22 Apr 200824 Apr 2008
Conference number: 11

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Number69160R
Volume4981
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop11th International Workshop on Hybrid Systems: Computation and Control, HSCC 2008
Abbreviated titleHSCC
CountryUnited States
CitySt. Louis
Period22/04/0824/04/08

Keywords

  • EWI-12140
  • IR-62226
  • METIS-250918

Cite this

Han, T., Katoen, J. P., & Mereacre, A. (2008). Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains. In Hybrid Systems: Computation and Control (HSCC) (pp. 244-258). [10.1007/978-3-540-78929-1] (Lecture Notes in Computer Science; Vol. 4981, No. 69160R). Berlin: Springer. https://doi.org/10.1007/978-3-540-78929-1_18, https://doi.org/10.1007/978-3-540-78929-1
Han, Tingting ; Katoen, Joost P. ; Mereacre, A. / Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains. Hybrid Systems: Computation and Control (HSCC). Berlin : Springer, 2008. pp. 244-258 (Lecture Notes in Computer Science; 69160R).
@inproceedings{4325b7cfc42f4078a85be64f887c868b,
title = "Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains",
abstract = "This paper presents a compositional framework for the modeling of interactive continuous-time Markov chains with time-dependent rates, a subclass of communicating piecewise deterministic Markov processes. A poly-time algorithm is presented for computing the coarsest quotient under strong bisimulation for rate functions that are either piecewise uniform or (piecewise) polynomial. Strong as well as weak bisimulation are shown to be congruence relations for the compositional framework, thus allowing component-wise minimization. In addition, a new characterization of transient probabilities in time-inhomogeneous Markov chains with piecewise uniform rates is provided.",
keywords = "EWI-12140, IR-62226, METIS-250918",
author = "Tingting Han and Katoen, {Joost P.} and A. Mereacre",
note = "10.1007/978-3-540-78929-1",
year = "2008",
month = "4",
doi = "10.1007/978-3-540-78929-1_18",
language = "Undefined",
isbn = "978-3-540-78928-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "69160R",
pages = "244--258",
booktitle = "Hybrid Systems: Computation and Control (HSCC)",

}

Han, T, Katoen, JP & Mereacre, A 2008, Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains. in Hybrid Systems: Computation and Control (HSCC)., 10.1007/978-3-540-78929-1, Lecture Notes in Computer Science, no. 69160R, vol. 4981, Springer, Berlin, pp. 244-258, 11th International Workshop on Hybrid Systems: Computation and Control, HSCC 2008, St. Louis, United States, 22/04/08. https://doi.org/10.1007/978-3-540-78929-1_18, https://doi.org/10.1007/978-3-540-78929-1

Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains. / Han, Tingting; Katoen, Joost P.; Mereacre, A.

Hybrid Systems: Computation and Control (HSCC). Berlin : Springer, 2008. p. 244-258 10.1007/978-3-540-78929-1 (Lecture Notes in Computer Science; Vol. 4981, No. 69160R).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains

AU - Han, Tingting

AU - Katoen, Joost P.

AU - Mereacre, A.

N1 - 10.1007/978-3-540-78929-1

PY - 2008/4

Y1 - 2008/4

N2 - This paper presents a compositional framework for the modeling of interactive continuous-time Markov chains with time-dependent rates, a subclass of communicating piecewise deterministic Markov processes. A poly-time algorithm is presented for computing the coarsest quotient under strong bisimulation for rate functions that are either piecewise uniform or (piecewise) polynomial. Strong as well as weak bisimulation are shown to be congruence relations for the compositional framework, thus allowing component-wise minimization. In addition, a new characterization of transient probabilities in time-inhomogeneous Markov chains with piecewise uniform rates is provided.

AB - This paper presents a compositional framework for the modeling of interactive continuous-time Markov chains with time-dependent rates, a subclass of communicating piecewise deterministic Markov processes. A poly-time algorithm is presented for computing the coarsest quotient under strong bisimulation for rate functions that are either piecewise uniform or (piecewise) polynomial. Strong as well as weak bisimulation are shown to be congruence relations for the compositional framework, thus allowing component-wise minimization. In addition, a new characterization of transient probabilities in time-inhomogeneous Markov chains with piecewise uniform rates is provided.

KW - EWI-12140

KW - IR-62226

KW - METIS-250918

U2 - 10.1007/978-3-540-78929-1_18

DO - 10.1007/978-3-540-78929-1_18

M3 - Conference contribution

SN - 978-3-540-78928-4

T3 - Lecture Notes in Computer Science

SP - 244

EP - 258

BT - Hybrid Systems: Computation and Control (HSCC)

PB - Springer

CY - Berlin

ER -

Han T, Katoen JP, Mereacre A. Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains. In Hybrid Systems: Computation and Control (HSCC). Berlin: Springer. 2008. p. 244-258. 10.1007/978-3-540-78929-1. (Lecture Notes in Computer Science; 69160R). https://doi.org/10.1007/978-3-540-78929-1_18, https://doi.org/10.1007/978-3-540-78929-1