TY - GEN
T1 - Simple O(m log n) time Markov chain lumping
AU - Valmari, Antti
AU - Franceschinis, Giuliana
PY - 2010
Y1 - 2010
N2 - In 2003, Derisavi, Hermanns, and Sanders presented a complicated O(m logn) time algorithm for the Markov chain lumping problem, where n is the number of states and m the number of transitions in the Markov chain. They speculated on the possibility of a simple algorithm and wrote that it would probably need a new way of sorting weights. In this article we present an algorithm of that kind. In it, the weights are sorted with a combination of the so-called possible majority candidate algorithm with any O(k logk) sorting algorithm. This works because, as we prove in the article, the weights consist of two groups, one of which is sufficiently small and all weights in the other group have the same value. We also point out an essential problem in the description of the earlier algorithm, prove the correctness of our algorithm in detail, and report some running time measurements.
AB - In 2003, Derisavi, Hermanns, and Sanders presented a complicated O(m logn) time algorithm for the Markov chain lumping problem, where n is the number of states and m the number of transitions in the Markov chain. They speculated on the possibility of a simple algorithm and wrote that it would probably need a new way of sorting weights. In this article we present an algorithm of that kind. In it, the weights are sorted with a combination of the so-called possible majority candidate algorithm with any O(k logk) sorting algorithm. This works because, as we prove in the article, the weights consist of two groups, one of which is sufficiently small and all weights in the other group have the same value. We also point out an essential problem in the description of the earlier algorithm, prove the correctness of our algorithm in detail, and report some running time measurements.
UR - http://www.scopus.com/inward/record.url?scp=77951558443&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-12002-2_4
DO - 10.1007/978-3-642-12002-2_4
M3 - Conference contribution
AN - SCOPUS:77951558443
SN - 3642120016
SN - 9783642120015
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 38
EP - 52
BT - Tools and Algorithms for the Construction and Analysis of Systems - 16th Int. Conf., TACAS 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Proc.
T2 - 16th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010
Y2 - 20 March 2010 through 28 March 2010
ER -