improved bounded model checking for the universal fragment of ctl
文献类型：期刊论文
| 作者 | Xu Liang ; Chen Wei ; Xu Yan-Yan ; Zhang Wen-Hui |
| 刊名 | JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
 |
| 出版日期 | 2009 |
| 卷号 | 24期号:1页码:96-109 |
| 关键词 | software verification model checking algorithm bounded model checking ACTL SAT |
| ISSN号 | 1000-9000 |
| 学科主题 | Computer Science ; Hardware & Architecture; Computer Science ; Software Engineering |
| WOS记录号 | WOS:000264619600011 |
| 公开日期 | 2011-03-18 |
| 附注 | SAT-based bounded model checking (BMC) has been introduced as a complementary technique to BDD-based symbolic model checking in recent years, and a lot of successful work has been done in this direction. The approach was first introduced by A. Biere et al. in checking linear temporal logic (LTL) formulae and then also adapted to check formulae of the universal fragment of computation tree logic (ACTL) by W. Penczek et al. As the efficiency of model checking is still an important issue, we present an improved BMC approach for ACTL based on Penczeks method. We consider two aspects of the approach. One is reduction of the number of variables and transitions in the k-model by distinguishing the temporal operator EX from the others. The other is simplification of the transformation of formulae by using uniform path encoding instead of a disjunction of all paths needed in the k-model. With these improvements, for an ACTL formula, the length of the final encoding of the formula in the worst case is reduced. The improved approach is implemented in the tool BMV and is compared with the original one by applying both to two well known examples, mutual exclusion and dining philosophers. The comparison shows the advantages of the improved approach with respect to the efficiency of model checking. |
| 源URL | [http://124.16.136.157/handle/311060/7698]  |
| 专题 | 软件研究所_计算机科学国家重点实验室 _期刊论文 |
| 推荐引用方式 GB/T 7714 | Xu Liang,Chen Wei,Xu Yan-Yan,et al. improved bounded model checking for the universal fragment of ctl[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2009,24(1):96-109. |
| APA | Xu Liang,Chen Wei,Xu Yan-Yan,&Zhang Wen-Hui.(2009).improved bounded model checking for the universal fragment of ctl.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,24(1),96-109. |
| MLA | Xu Liang,et al."improved bounded model checking for the universal fragment of ctl".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 24.1(2009):96-109. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。