Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Simple O(m logn) Time Markov Chain Lumping
verfasst von : Antti Valmari, Giuliana Franceschinis
Erschienen in: Tools and Algorithms for the Construction and Analysis of Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.