一种基于离散时间自动机的LTL性质检测工具  

A Model Checking Tool Based on Discrete Timed Automata

作　　者：张文亮[1] 彭云全[1] 

机构地区：[1]中国科学院软件研究所计算机科学国家重点实验室

出　　处：《计算机仿真》2008年第4期80-83,共4页Computer Simulation

基　　金：国家自然科学基金资助项目(60673051,60421001);国家973计划资助项目(2002cb312200)

摘　　要：模型检测是一种自动完成性质验证的算法过程,在模型检测过程中会遇到状态空间爆炸的问题,即随系统规模的增长状态空间的大小呈指数增长,如何缓解此问题一直是研究者研究的重点。目前利用模型检测方法对线性时序逻辑(LTL)性质进行检测的工具还比较少,且效率都较低。介绍了一种基于离散时间自动机的LTL性质检测工具,采用了在状态空间中存储延迟序列(DS)的技术,对状态进行压缩存储,减小了时间空间的消耗,加快了检测速度。实验表明,该工具的检测效果是不错的,要好于同类工具,如DTSpin。Model checking is an automatic technique for verifying finite state systems. The main challenge in model checking is dealing with the space explosion problem, that is, the size of the state space of a system may be exponential in the size of the system. At present there aren＇t many model checking tools for checking properties described by linear temporal logic （LTL） , which often have bad performance. This paper introduces a model checking tool for discrete timed automata, which can check an LTL property. A data structure named DS （ Delay Sequence） is used to deduce the state space and time consumption in the process of state - space generation. The experiment resuits show that this tool is more effective than other similar tools, such as DTSpin.

关 键 词：离散时间自动机 非空性检测 线性时序逻辑性质 

分 类 号：N945.12[自然科学总论—系统科学]