Incremental bisimulation abstraction refinement

ISCAS OpenIR

	Incremental bisimulation abstraction refinement
	Song, Lei (1); Zhang, Lijun (2); Hermanns, Holger (1); Godskesen, Jens Chr. (3)
	2013
会议名称	2013 13th International Conference on Application of Concurrency to System Design, ACSD 2013
页码	11-20
会议日期	July 8, 2013 - July 10, 2013
会议地点	Barcelona, Spain
收录类别	SCI ; EI
出版地	Institute of Electrical and Electronics Engineers Inc., 3 Park Avenue, 17th Floor, New York, NY 10016-5997, United States
ISSN	15504808
ISBN	9780769550350
部门归属	(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
摘要	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.
关键词	Algorithms Experimentation Verification Bisimulation Cegar Probabilistic Automata
语种	英语
WOS记录号	WOS:000341390100025
引用统计
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16502
专题	中国科学院软件研究所
推荐引用方式 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.