Lumpability for Uncertain Continuous-Time Markov Chains

Luca Cardelli, Radu Grosu, Kim Guldstrand Larsen, Mirco Tribastone, Max Tschaikowski, Andrea Vandin

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

2 Citations (Scopus)

Abstract

The assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. In this paper we consider uncertain CTMCs, where rates are assumed to vary non-deterministically with time from bounded continuous intervals. This leads to a semantics which associates each state with the reachable set of its probability under all possible choices of the uncertain rates. We develop a notion of lumpability which identifies a partition of states where each block preserves the reachable set of the sum of its probabilities, essentially lifting the well-known CTMC ordinary lumpability to the uncertain setting. We proceed with this analogy with two further contributions: a logical characterization of uncertain CTMC lumping in terms of continuous stochastic logic; and a polynomial time and space algorithm for the minimization of uncertain CTMCs by partition refinement, using the CTMC lumping algorithm as an inner step. As a case study, we show that the minimizations in a substantial number of CTMC models reported in the literature are robust with respect to uncertainties around their original, fixed, rate values.
Original languageEnglish
Title of host publicationQuantitative Evaluation of Systems : 18th International Conference, QEST 2021, Paris, France, August 23–27, 2021, Proceedings
PublisherSpringer
Publication date2021
Pages391-409
ISBN (Print)978-3-030-85171-2
ISBN (Electronic)978-3-030-85172-9
DOIs
Publication statusPublished - 2021
EventInternational Conference on Quantitative Evaluation of Systems - Paris, France
Duration: 23 Aug 202127 Aug 2021

Conference

ConferenceInternational Conference on Quantitative Evaluation of Systems
Country/TerritoryFrance
CityParis
Period23/08/202127/08/2021
SeriesLecture Notes in Computer Science
Volume12846
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Lumpability for Uncertain Continuous-Time Markov Chains'. Together they form a unique fingerprint.

Cite this