2010 | OriginalPaper | Chapter
Simple O(m logn) Time Markov Chain Lumping
Authors : Antti Valmari, Giuliana Franceschinis
Published in: Tools and Algorithms for the Construction and Analysis of Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In 2003, Derisavi, Hermanns, and Sanders presented a complicated
O
(
m
log
n
) 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
log
k
) 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.