Distributed Qualitative LTL Model Checking of Markov Decision Processes

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BARNAT Jiří BRIM Luboš ČERNÁ Ivana ČEŠKA Milan TŮMOVÁ Jana

Year of publication 2006
Type Article in Proceedings
Conference Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords distributed; parallel; LTL model checking; probabilistic systems; MDP
Description Markov decision processes are used to model concurrent programs that exhibit uncertainty. The state explosion problem for probabilistic systems is more critical than in the non-probabilistic case. In the paper we propose a cluster-based algorithm for qualitative LTL model checking of finite state Markov decision processes. We use the automata approach which reduces the model checking problem to the question of existence of an accepting end component. The algorithm uses repeated reachability which systematically eliminates states that cannot belong to any accepting end component. A distinguished feature of the distributed algorithm is that its complexity meets the complexity of the best known sequential algorithm.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.