Computing Probability Lower and Upper Bounds for LTL Formulae over Sequential and Concurrent Markov Chains

Baier, Christel ; Kwiatkowska, Marta ; Norman, Gethin

Document Type: Conference or workshop publication
Year of publication: 1999
Book title: PROBMIV'98, First International Workshop on Probabilistic Methods in Verification : proceedings
The title of a journal, publication series: Electronic Notes in Theoretical Computer Science : ENTCS
Volume: 22
Author/Publisher of the book
(only the first ones mentioned)
Baier, Christel
Place of publication: Amsterdam [u.a.]
Publishing house: Elsevier
ISSN: 1571-0661
Publication language: English
Institution: School of Business Informatics and Mathematics > Praktische Informatik II (Majster-Cederbaum Em)
Subject: 004 Computer science, internet
Abstract: 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.

+ Export and Citation

Choose a citation style.

+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item