Optimal state-space lumping in Markov chains


Derisavi, Salem and Hermanns, Holger and Sanders, William H. (2003) Optimal state-space lumping in Markov chains. Information Processing Letters, 87 (6). pp. 309-315. ISSN 0020-0190

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Article
Copyright:© 2003 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/75030
Official URL:https://doi.org/10.1016/S0020-0190(03)00343-0
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page