|
|||||
|
|
Optimal state-space lumping in Markov chains |
|
| Authors: | Salem Derisavi Holger Hermanns William H. Sanders |
| Affiliation: | a University of Illinois at Urbana-Champaign, Coordinated Science Laboratory, Urbana, IL 61801, USA b University of Twente, Faculty of Computer Science, 7500 AE Enschede, The Netherlands c Universität des Saarlandes, FR 6.2 Informatik, D-66123 Saarbrücken, Germany |
| Abstract: | We prove that the optimal lumping quotient of a finite Markov chain can be constructed in O(mlgn) time, where n is the number of states and m is the number of transitions. Our proof relies on the use of splay trees (designed by Sleator and Tarjan [J. ACM 32 (3) (1985) 652-686]) to sort transition weights. |
| Keywords: | Bisimulation Computational complexity Lumpability Markov chains Splay trees |
| 本文献已被 ScienceDirect 等数据库收录！ | |