| BARNAT, Jiří, Luboš BRIM, Ivana ČERNÁ, Milan ČEŠKA a Jana TŮMOVÁ. Distributed Qualitative LTL Model Checking of Markov Decision Processes. In Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation. Bonn, Germany: University of Bonn, 2006, s. 1-15. ISSN 1571-0661. |
Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{702452,
author = {Barnat, Jiří and Brim, Luboš and Černá, Ivana and Češka, Milan and Tůmová, Jana},
address = {Bonn, Germany},
booktitle = {Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation},
keywords = {distributed; parallel; LTL model checking; probabilistic systems; MDP},
language = {eng},
location = {Bonn, Germany},
pages = {1-15},
publisher = {University of Bonn},
title = {Distributed Qualitative LTL Model Checking of Markov Decision Processes},
year = {2006}
}
TY - JOUR
ID - 702452
AU - Barnat, Jiří - Brim, Luboš - Černá, Ivana - Češka, Milan - Tůmová, Jana
PY - 2006
TI - Distributed Qualitative LTL Model Checking of Markov Decision Processes
PB - University of Bonn
CY - Bonn, Germany
KW - distributed
KW - parallel
KW - LTL model checking
KW - probabilistic systems
KW - MDP
N2 - 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.
ER -
BARNAT, Jiří, Luboš BRIM, Ivana ČERNÁ, Milan ČEŠKA a Jana TŮMOVÁ. Distributed Qualitative LTL Model Checking of Markov Decision Processes. In \textit{Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation}. Bonn, Germany: University of Bonn, 2006, s.~1-15. ISSN~1571-0661.
|
