Computing Conditional Probabilities in Markovian Models Efficiently
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
The fundamentals of probabilistic model checking for Markovian models and temporal properties have been studied extensively in the past 20 years. Research on methods for computing conditional probabilities for temporal properties under temporal conditions is, however, comparably rare. For computing conditional probabilities or expected values under ω-regular conditions in Markov chains, we introduce a new transformation of Markov chains that incorporates the effect of the condition into the model. For Markov decision processes, we show that the task to compute maximal reachability probabilities under reachability conditions is solvable in polynomial time, while it was conjectured to be computationally hard. Using adaptions of known automata-based methods, our algorithm can be generalized for computing the maximal conditional probabilities for ω-regular events under ω-regular conditions. The feasibility of our algorithms is studied in two benchmark examples.
Details
Original language | English |
---|---|
Title of host publication | Tools and Algorithms for the Construction and Analysis of Systems |
Editors | Erika Ábrahám, Klaus Havelund |
Publisher | Springer, Berlin [u. a.] |
Pages | 515-530 |
Number of pages | 16 |
ISBN (print) | 978-3-642-54861-1 |
Publication status | Published - 2014 |
Peer-reviewed | Yes |
Publication series
Series | Lecture Notes in Computer Science, Volume 8413 |
---|---|
ISSN | 0302-9743 |
Conference
Title | European Joint Conferences on Theory and Practice of Software 2014 |
---|---|
Abbreviated title | ETAPS 2014 |
Conference number | 17 |
Duration | 5 - 13 April 2014 |
Website | |
Degree of recognition | International event |
Location | Grenoble World Trade Center |
City | Grenoble |
Country | France |
External IDs
Scopus | 84900534492 |
---|---|
ORCID | /0000-0002-5321-9343/work/142236741 |
ORCID | /0000-0003-1724-2586/work/165453605 |
Keywords
DFG Classification of Subject Areas according to Review Boards
Subject groups, research areas, subject areas according to Destatis
Keywords
- conditional probabilities, Markovian Models