Distributed Qualitative LTL Model Checking of Markov Decision Processes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00015450" target="_blank" >RIV/00216224:14330/06:00015450 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Distributed Qualitative LTL Model Checking of Markov Decision Processes
Original language 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.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation
ISBN
—
ISSN
1571-0661
e-ISSN
—
Number of pages
15
Pages from-to
—
Publisher name
University of Bonn
Place of publication
Bonn, Germany
Event location
Bonn
Event date
Jan 1, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)