Institutional Repository
| Incremental bisimulation abstraction refinement | |
| Song, Lei (1); Zhang, Lijun (2); Hermanns, Holger (1); Godskesen, Jens Chr. (3) | |
| 2013 | |
| Conference Name | 2013 13th International Conference on Application of Concurrency to System Design, ACSD 2013 |
| Pages | 11-20 |
| Conference Date | July 8, 2013 - July 10, 2013 |
| Conference Place | Barcelona, Spain |
| Indexed Type | SCI ; EI |
| Publish Place | Institute of Electrical and Electronics Engineers Inc., 3 Park Avenue, 17th Floor, New York, NY 10016-5997, United States |
| ISSN | 15504808 |
| ISBN | 9780769550350 |
| Department | (1) Saarland University, Germany; (2) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; (3) IT University of Copenhagen, Denmark; (4) Max-Planck-Institut für Informatik, Saarbrücken, Germany |
| English Abstract | Abstraction refinement techniques in probabilistic model checking are prominent approaches to the verification of very large or infinite-state probabilistic concurrent systems. At the core of the refinement step lies the implicit or explicit analysis of a counterexample. This paper proposes an abstraction refinement approach for the probabilistic computation tree logic (PCTL), which is based on incrementally computing a sequence of may- and must-quotient automata. These are induced by depth-bounded bisimulation equivalences of increasing depth. The approach is both sound and complete, since the equivalences converge to the genuine PCTL equivalence. Experimental results with a prototype implementation show the effectiveness of the approach. © 2013 IEEE.; Abstraction refinement techniques in probabilistic model checking are prominent approaches to the verification of very large or infinite-state probabilistic concurrent systems. At the core of the refinement step lies the implicit or explicit analysis of a counterexample. This paper proposes an abstraction refinement approach for the probabilistic computation tree logic (PCTL), which is based on incrementally computing a sequence of may- and must-quotient automata. These are induced by depth-bounded bisimulation equivalences of increasing depth. The approach is both sound and complete, since the equivalences converge to the genuine PCTL equivalence. Experimental results with a prototype implementation show the effectiveness of the approach. © 2013 IEEE. |
| Keyword | Algorithms Experimentation Verification Bisimulation Cegar Probabilistic Automata |
| Language | 英语 |
| WOS ID | WOS:000341390100025 |
| Citation statistics | |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16502 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Song, Lei ,Zhang, Lijun ,Hermanns, Holger ,et al. Incremental bisimulation abstraction refinement[C]. Institute of Electrical and Electronics Engineers Inc., 3 Park Avenue, 17th Floor, New York, NY 10016-5997, United States,2013:11-20. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment