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

PDF
Restricted to UT campus only: Request a copy
117Kb

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
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Formal Methods and Tools (FMT)
Link to this item:	http://purl.utwente.nl/publications/75030
Official URL:	http://dx.doi.org/10.1016/S0020-0190(03)00343-0
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page