@article{e425a189babd488fba91e77c4e1f950c,
title = "Optimal state-space lumping in Markov chains",
abstract = "A study on optimal state-space lumping in Markov chains is presented. It is proved that the optimal lumping quotient of a finite Markov chain can be constructed in O(m lg n) time, where n is the number of states and m is the number of transitions. The proof relies on the use of splay trees to sort transition weights.",
keywords = "Bisimulation, Computational complexity, Lumpability, Markov chains, Splay trees",
author = "Salem Derisavi and Holger Hermanns and Sanders, {William H.}",
note = "Funding Information: ✩ This material is based upon work supported by the National Science Foundation under Grant Nos. 9975019 and 0086096, by the Motorola Center for High-Availability System Validation at the University of Illinois (under the umbrella of the Motorola Communications Center), and by the Netherlands Organization for Scientific Research through a Vernieuwingsimpuls award. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors. * Corresponding author. E-mail addresses: derisavi@crhc.uiuc.edu (S. Derisavi), hermanns@cs.utwente.nl (H. Hermanns), whs@crhc.uiuc.edu (W.H. Sanders).",
year = "2003",
month = sep,
day = "30",
doi = "10.1016/S0020-0190(03)00343-0",
language = "English (US)",
volume = "87",
pages = "309--315",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "6",
}