Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-38613-8_12
Title: Improved reachability analysis in DTMC via divide and conquer
Authors: Song, S.
Gui, L.
Sun, J.
Liu, Y.
Dong, J.S. 
Issue Date: 2013
Citation: Song, S.,Gui, L.,Sun, J.,Liu, Y.,Dong, J.S. (2013). Improved reachability analysis in DTMC via divide and conquer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7940 LNCS : 162-176. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-38613-8_12
Abstract: Discrete Time Markov Chains (DTMCs) are widely used to model probabilistic systems in many domains, such as biology, network and communication protocols. There are two main approaches for probability reachability analysis of DTMCs, i.e., solving linear equations or using value iteration. However, both approaches have drawbacks. On one hand, solving linear equations can generate accurate results, but it can be only applied to relatively small models. On the other hand, value iteration is more scalable, but often suffers from slow convergence. Furthermore, it is unclear how to parallelize (i.e., taking advantage of multi-cores or distributed computers) these two approaches. In this work, we propose a divide-and-conquer approach to eliminate loops in DTMC and hereby speed up probabilistic reachability analysis. A DTMC is separated into several partitions according to our proposed cutting criteria. Each partition is then solved by Gauss-Jordan elimination effectively and the state space is reduced afterwards. This divide and conquer algorithm will continue until there is no loop existing in the system. Experiments are conducted to demonstrate that our approach can generate accurate results, avoid the slow convergence problems and handle larger models. © 2013 Springer-Verlag Berlin Heidelberg.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/78185
ISBN: 9783642386121
ISSN: 03029743
DOI: 10.1007/978-3-642-38613-8_12
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

4
checked on Nov 16, 2018

Page view(s)

44
checked on Oct 27, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.