Logo der Universität Wien

Faster and Dynamic Algorithms For Maximal End-Component Decomposition And Related Graph Problems In Probabilistic Verification

Abstract

We present faster and dynamic algorithms for the following problems arising in probabilistic veri?cation: Computation of the maximal end-component (mec) decomposition of Markov decision processes (MDPs), and of the almost sure winning set for reachability and parity ob jectives in MDPs. We achieve the following running time for static algorithms in MDPs with graphs of n vertices and m edges: (1) O(m

Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna