Probabilistic verification of sequential and concurrent Markov chains against linear time specifications is known to be expensive in terms of time and space: time is exponential in the size of the formula and polynomial in the size of the state space [Var85, CY95]. This paper proposes a more efficient alternative to compute for a linear time formula only a lower and upper bound on the probability measure of the set of paths satisfying it, instead of calculating the exact probability. This yields a coarser estimate, namely an interval of values contained in [0,1] to which the actual probability belongs, but is much faster (polynomial in the size of the formula and the state space), and could thus be useful as an initial check in a model checking tool.
Additional information:
Online Ressource
Dieser Eintrag ist Teil der Universitätsbibliographie.
Search Authors in