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


Baier, Christel ; Kwiatkowska, Marta ; Norman, Gethin


URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=1...
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.




+ Citation Example and Export

Baier, Christel ; Kwiatkowska, Marta ; Norman, Gethin Computing Probability Lower and Upper Bounds for LTL Formulae over Sequential and Concurrent Markov Chains. Baier, Christel Electronic Notes in Theoretical Computer Science : ENTCS 22 In: PROBMIV'98, First International Workshop on Probabilistic Methods in Verification : proceedings (1999) Amsterdam [u.a.] [Conference or workshop publication]


+ 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