TY - GEN
T1 - Automated Markov-chain based analysis for large state spaces
AU - Smith, Kaitlin N.
AU - Taylor, Michael A.
AU - Carroll, Anna A.
AU - Manikas, Theodore W.
AU - Thornton, Mitchell A.
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/5/26
Y1 - 2017/5/26
N2 - Modeling the dynamic, time-varying behavior of systems and processes is a common design and analysis task in the systems engineering community. A popular method for performing such analysis is the use of Markov chains. Additionally, automated methods may be used to automatically determine new system state values for a system under observation or test. Unfortunately, the state-transition space of a Markov chain grows exponentially in the number of states resulting in limitations in the use of Markov chains for dynamic analysis. We present results in the use of an efficient data structure, the algebraic decision diagram (ADD), for representation of Markov chains and an accompanying prototype analysis tool. Experimental results are provided that indicate the ADD is a viable structure to enable the automated modeling of Markov chains consisting of hundreds of thousands of states due to their ability to provide computation related efficiencies. This result allows automated Markov chain analysis of extremely large state spaces to be a viable technique for system and process modeling and analysis. Experimental results from a prototype implementation of an ADD-based analysis tool are provided to substantiate our conclusions.
AB - Modeling the dynamic, time-varying behavior of systems and processes is a common design and analysis task in the systems engineering community. A popular method for performing such analysis is the use of Markov chains. Additionally, automated methods may be used to automatically determine new system state values for a system under observation or test. Unfortunately, the state-transition space of a Markov chain grows exponentially in the number of states resulting in limitations in the use of Markov chains for dynamic analysis. We present results in the use of an efficient data structure, the algebraic decision diagram (ADD), for representation of Markov chains and an accompanying prototype analysis tool. Experimental results are provided that indicate the ADD is a viable structure to enable the automated modeling of Markov chains consisting of hundreds of thousands of states due to their ability to provide computation related efficiencies. This result allows automated Markov chain analysis of extremely large state spaces to be a viable technique for system and process modeling and analysis. Experimental results from a prototype implementation of an ADD-based analysis tool are provided to substantiate our conclusions.
KW - ADD
KW - Algebraic Decision Diagram
KW - dynamic system analysis
KW - Markov chain
KW - reliability analysis tool
UR - http://www.scopus.com/inward/record.url?scp=85021438937&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85021438937&partnerID=8YFLogxK
U2 - 10.1109/SYSCON.2017.7934746
DO - 10.1109/SYSCON.2017.7934746
M3 - Conference contribution
AN - SCOPUS:85021438937
T3 - 11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings
BT - 11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 11th Annual IEEE International Systems Conference, SysCon 2017
Y2 - 24 April 2017 through 27 April 2017
ER -