This paper optimizes the encoding of verifying G(p) and G(p→F(q)) which are two important and frequently used modal operators in optimization of encoding for bounded model checking (BMC). Through analysis of the properties of finite state machine (FSM) and LTL (linear-time temporal logic) when verifying these modal operators, it presents a concise recursive formula, which can efficiently translate BMC instances into SAT (satisfiability) instances. The logical properties of these recursion formulas are verified. The experimental comparison between the optimization of BMC and the other two important methods AA_BMC and Timo_BMC for solving these modal operators in BMC shows that the former is superior to the latter in both the scale of instances and the difficulty to solve the problem. Research of this paper is also beneficial to encoding optimization of verifying other modal operators in BMC.
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.