The Compositional Construction of Markov Processes |
| |
Authors: | Luisa de Francesco Albasini Nicoletta Sabadini Robert F. C. Walters |
| |
Affiliation: | (1) Department of Computer Science and Engineering, Chalmers University of Technology, 41296 Gothenburg, Sweden;(2) Cadence Research Labs, 2150 Shattuck Avenue, 10th Floor, Berkeley, CA 94704, USA;(3) Department of Signals and Systems, Chalmers University of Technology, 41296 Gothenburg, Sweden |
| |
Abstract: | We describe a symmetric monoidal category whose arrows are automata in which the actions have probabilities. The endomorphisms of the identity for the tensor are classical finite Markov processes. The operations of the category permit the compositional description Markov processes. We illustrate by describing a Markov process with 12 n states, which represents a model of the classical Dining Philosopher problem with n dining philosophers, showing how to calculate the probability of reaching deadlock in k steps. A straightforward application of the Perron-Frobenius Theorem yields that this probability tends to 1 as k tends to infinity. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|