×

zbMATH — the first resource for mathematics

A symbolic algorithm for optimal Markov chain lumping. (English) Zbl 1186.68324
Grumberg, Orna (ed.) et al., Tools and algorithms for the construction and analysis of systems. 13th international conference, TACAS 2007, held as part of the joint European conferences on theory and practice of software, ETAPS 2007, Braga, Portugal, March 24 – April 1, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-71208-4/pbk). Lecture Notes in Computer Science 4424, 139-154 (2007).
Summary: Many approaches to tackle the state explosion problem of Markov chains are based on the notion of lumpability, which allows computation of measures using the quotient Markov chain, which, in some cases, has much smaller state space than the original one. We present, for the first time, a symbolic algorithm and its implementation for the lumping of Markov chains that are represented using Multi-Terminal Binary Decision Diagrams. The algorithm is optimal, i.e., generates the smallest possible quotient Markov chain. Our experiments on various configurations of two example models show that the algorithm (1) handles significantly larger state spaces than an explicit algorithm, (2) is in the best case, faster than an efficient explicit algorithm while not prohibitively slower in the worst case, and (3) generates quotient Markov chains that are several orders of magnitude smaller than ones generated by a model-dependent symbolic lumping algorithm.
For the entire collection see [Zbl 1116.68006].
Reviewer: Reviewer (Berlin)

MSC:
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68P05 Data structures
68W30 Symbolic computation and algebraic computation
Software:
PRISM; SIGREF
PDF BibTeX XML Cite
Full Text: DOI