Name
Abstract | ||
|---|---|---|
The mathematical concept of Markov chains is widely used to model and analyze many engineering and scientific problems. Markovian models are usually analyzed using computer simulation, and more recently using probabilistic model-checking but these methods either do not guarantee accurate analysis or are not scalable. As an alternative, we propose to use higher-order-logic theorem proving to reason about properties of systems that can be described as Markov chains. As the first step towards this goal, this paper presents a formalization of time homogeneous finite-state Discrete-time Markov chains and the formal verification of some of their fundamental properties, such as Joint probabilities, Chapman-Kolmogorov equation and steady state probabilities, using the HOL theorem prover. For illustration purposes, we utilize our formalization to analyze a simplified binary communication channel. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-24372-1_8 | ATVA |
Keywords | Field | DocType |
finite-state discrete-time markov chain,joint probability,hol theorem prover,markovian model,binary communication channel,accurate analysis,higher-order-logic theorem,markov chain,chapman-kolmogorov equation,computer simulation,formal verification | HOL,Discrete mathematics,Joint probability distribution,Markov process,Computer science,Automated theorem proving,Markov chain,Algorithm,Theoretical computer science,Probabilistic logic,Discrete time and continuous time,Formal verification | Conference |
Volume | ISSN | Citations |
6996 | 0302-9743 | 8 |
PageRank | References | Authors |
0.62 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| liya liu | 1 | 20 | 2.42 |
| Osman Hasan | 2 | 401 | 60.79 |
| Sofiène Tahar | 3 | 915 | 110.41 |