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