Zhang, Lijun and Hermanns, Holger and Eisenbrand, Friedrich and Jansen, David N. - Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations

lmcs:989 - Logical Methods in Computer Science, November 11, 2008, Volume 4, Issue 4
Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations

Authors: Zhang, Lijun and Hermanns, Holger and Eisenbrand, Friedrich and Jansen, David N.

Strong and weak simulation relations have been proposed for Markov chains, while strong simulation and strong probabilistic simulation relations have been proposed for probabilistic automata. However, decision algorithms for strong and weak simulation over Markov chains, and for strong simulation over probabilistic automata are not efficient, which makes it as yet unclear whether they can be used as effectively as their non-probabilistic counterparts. This paper presents drastically improved algorithms to decide whether some (discrete- or continuous-time) Markov chain strongly or weakly simulates another, or whether a probabilistic automaton strongly simulates another. The key innovation is the use of parametric maximum flow techniques to amortize computations. We also present a novel algorithm for deciding strong probabilistic simulation preorders on probabilistic automata, which has polynomial complexity via a reduction to an LP problem. When extending the algorithms for probabilistic automata to their continuous-time counterpart, we retain the same complexity for both strong and strong probabilistic simulations.


Source : oai:arXiv.org:0808.3651
DOI : 10.2168/LMCS-4(4:6)2008
Volume: Volume 4, Issue 4
Published on: November 11, 2008
Submitted on: June 25, 2015
Keywords: Computer Science - Logic in Computer Science,F.2.1,F.3.1,G.2.2,G.3


Share

Browsing statistics

This page has been seen 15 times.
This article's PDF has been downloaded 9 times.