### Abstract

A large variety of computer and communication systems can be modeled adequately as infinite-state continuous-time Markov chains (CTMCs). A highly structured class of such infinite-state CTMCs is the class of Quasi-Birth-Death processes (QBDs), on which we focus in this paper. We present an efficient variant of uniformization for computing the transient probability $\mathbf{V}_{i,j}(t)$ of being in each state $j$ of the QBD for any possible initial state $i$ at time $t$. Note that both the set of starting states and the set of goal states have infinite size. All the probabilities $\mathbf{V}_{i,j}(t)$ are needed in the context of probabilistic model checking. The key idea of our algorithm is to split the infinite set of starting states into a finite part and an infinite (repeating) part. The transient probabilities for the infinite part are then computed using the new notion of \emph{representatives}. We present the required data structures and algorithm, as well as an application-dependent optimal stopping criterion. In a simple case study we show the feasibility of our approach, as well as the efficiency gain due to the optimal stopping criterion.

Original language | English |
---|---|

Publisher | Association for Computing Machinery (ACM) |

Place of Publication | New York |

ISBN (Print) | 1-59593-506-1 |

DOIs | |

Publication status | Published - 11 Oct 2006 |

Externally published | Yes |

### Keywords

- METIS-238165
- EWI-6897
- IR-66348

## Fingerprint Dive into the research topics of 'Uniformization with Representatives - comprehensive transient analysis of infinite-state QBDs'. Together they form a unique fingerprint.

## Cite this

Remke, A. K. I., Haverkort, B. R. H. M., & Cloth, L. (2006, Oct 11). Uniformization with Representatives - comprehensive transient analysis of infinite-state QBDs.

*New York: Association for Computing Machinery (ACM)*. https://doi.org/10.1145/1190366.1190372