Sliding-window abstraction for infinite Markov chains

T.A. Henzinger, M. Mateescu, V. Wolf, in:, Springer, 2009, pp. 337–352.

Download
OA 804.29 KB

Conference Paper | Published
Series Title
LNCS
Abstract
We present an on-the-fly abstraction technique for infinite-state continuous -time Markov chains. We consider Markov chains that are specified by a finite set of transition classes. Such models naturally represent biochemical reactions and therefore play an important role in the stochastic modeling of biological systems. We approximate the transient probability distributions at various time instances by solving a sequence of dynamically constructed abstract models, each depending on the previous one. Each abstract model is a finite Markov chain that represents the behavior of the original, infinite chain during a specific time interval. Our approach provides complete information about probability distributions, not just about individual parameters like the mean. The error of each abstraction can be computed, and the precision of the abstraction refined when desired. We implemented the algorithm and demonstrate its usefulness and efficiency on several case studies from systems biology.
Publishing Year
Date Published
2009-01-01
Acknowledgement
The research has been partially funded by the Swiss National Science Foundation under grant 205321-111840.
Volume
5643
Page
337 - 352
Conference
CAV: Computer Aided Verification
IST-REx-ID

Cite this

Henzinger TA, Mateescu M, Wolf V. Sliding-window abstraction for infinite Markov chains. In: Vol 5643. Springer; 2009:337-352. doi:10.1007/978-3-642-02658-4_27
Henzinger, T. A., Mateescu, M., & Wolf, V. (2009). Sliding-window abstraction for infinite Markov chains (Vol. 5643, pp. 337–352). Presented at the CAV: Computer Aided Verification, Springer. https://doi.org/10.1007/978-3-642-02658-4_27
Henzinger, Thomas A, Maria Mateescu, and Verena Wolf. “Sliding-Window Abstraction for Infinite Markov Chains,” 5643:337–52. Springer, 2009. https://doi.org/10.1007/978-3-642-02658-4_27.
T. A. Henzinger, M. Mateescu, and V. Wolf, “Sliding-window abstraction for infinite Markov chains,” presented at the CAV: Computer Aided Verification, 2009, vol. 5643, pp. 337–352.
Henzinger TA, Mateescu M, Wolf V. 2009. Sliding-window abstraction for infinite Markov chains. CAV: Computer Aided Verification, LNCS, vol. 5643. 337–352.
Henzinger, Thomas A., et al. Sliding-Window Abstraction for Infinite Markov Chains. Vol. 5643, Springer, 2009, pp. 337–52, doi:10.1007/978-3-642-02658-4_27.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:12:20Z


Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar