Back to Search
Start Over
Importance Sampling for Stochastic Timed Automata
- Source :
- Lecture Notes in Computer Science, Dependable Software Engineering: Theories, Tools, and Applications ISBN: 9783319476766, SETTA, Dependable Software Engineering: Theories, Tools, and Applications, Dependable Software Engineering: Theories, Tools, and Applications, Nov 2016, Beijing, China, Jegourel, C, Larsen, K G, Legay, A, Mikučionis, M, Poulsen, D B & Sedwards, S 2016, Importance Sampling for Stochastic Timed Automata . in M Fränzle, D Kapur & N Zhan (eds), Dependable Software Engineering : Theories, Tools, and Applications . Springer, Lecture Notes in Computer Science, vol. 9984, pp. 163-178, Symposium on Dependable Software Engineering Theories, Tools and Applications, Beijing, China, 09/11/2016 . https://doi.org/10.1007/978-3-319-47677-3_11, Lecture Notes in Computer Science-Dependable Software Engineering: Theories, Tools, and Applications
- Publication Year :
- 2016
-
Abstract
- International audience; We present an importance sampling framework that combines symbolic analysis and simulation to estimate the probability of rare reachability properties in stochastic timed automata. By means of symbolic exploration, our framework first identifies states that cannot reach the goal. A state-wise change of measure is then applied on-the-fly during simulations, ensuring that dead ends are never reached. The change of measure is guaranteed by construction to reduce the variance of the estimator with respect to crude Monte Carlo, while experimental results demonstrate that we can achieve substantial computational gains.
- Subjects :
- Model checking
030213 general clinical medicine
0209 industrial biotechnology
stochastic timed automata
Computer science
Monte Carlo method
Timed automaton
Estimator
[INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE]
02 engineering and technology
Symbolic data analysis
model checking
rare events
[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF]
03 medical and health sciences
importance sampling
020901 industrial engineering & automation
0302 clinical medicine
Reachability
Rare events
verification
Algorithm
Importance sampling
Subjects
Details
- ISBN :
- 978-3-319-47676-6
978-3-319-47677-3 - ISSN :
- 03029743 and 16113349
- ISBNs :
- 9783319476766 and 9783319476773
- Database :
- OpenAIRE
- Journal :
- Lecture Notes in Computer Science
- Accession number :
- edsair.doi.dedup.....eb41c16fb7360297b845d575e18fd729
- Full Text :
- https://doi.org/10.1007/978-3-319-47677-3_11