Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Buch/Sammelband/Gutachten › Beigetragen › Begutachtung
Beitragende
Abstract
This paper introduces Farkas certificates for lower and upper bounds on minimal and maximal reachability probabilities in Markov decision processes (MDP), which we derive using an MDP-variant of Farkas’ Lemma. The set of all such certificates is shown to form a polytope whose points correspond to witnessing subsystems of the model and the property. Using this correspondence we can translate the problem of finding minimal witnesses to the problem of finding vertices with a maximal number of zeros. While computing such vertices is computationally hard in general, we derive new heuristics from our formulations that exhibit competitive performance compared to state-of-the-art techniques. As an argument that asymptotically better algorithms cannot be hoped for, we show that the decision version of finding minimal witnesses is NP-complete even for acyclic Markov chains.
Details
Originalsprache | Englisch |
---|---|
Titel | Tools and Algorithms for the Construction and Analysis of Systems |
Redakteure/-innen | Armin Biere, David Parker |
Herausgeber (Verlag) | Springer, Berlin [u. a.] |
Seiten | 324–345 |
ISBN (Print) | 978-3-030-45189-9 |
Publikationsstatus | Veröffentlicht - 2020 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | Lecture Notes in Computer Science, Volume 12078 |
---|---|
ISSN | 0302-9743 |
Konferenz
Titel | 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems |
---|---|
Kurztitel | TACAS 2020 |
Veranstaltungsnummer | |
Dauer | 25 - 30 April 2020 |
Bekanntheitsgrad | Internationale Veranstaltung |
Ort | |
Stadt | Dublin |
Land | Irland |
Externe IDs
Scopus | 85083956795 |
---|