文章编号 :1009 - 3486(2004)05 - 0010 - 04
时 态 逻 辑 形 式 化 描 述 并发 系 统 性 质
倡 栘
肖美华
1 ,2 ,3
,薛锦云
1 ,3
(1 .江西师范大学 计算机信息工程学院 ,江西 南昌 330027 ;2 .南昌大学 计算中心 ,江西 南昌 330029 ;
3 .中国科学院软件研究所 计算机科学重点实验室 ,北京 100080)
摘 要 :时态逻辑是一种描述反应式(并发)系统中状态迁移序列的形式化方法 ,用于刻画并发系统所需验证
的性质 ,是模型检测的基础 .阐述了时态逻辑 CTL
倡
及其子逻辑 CTL 、LTL 的语法及语义 ,然后分析运用时态
逻辑描述并发系统性质 ,最后给出一个应用实例 .
关键词 :形式化方法 ;并发系统 ;时态逻辑 ;模型检测
中图分类号 : TP302 .2 文献标识码 : A
Formal description of properties of concurrency system by temporal logic
XIAO Mei‐hua
1 ,2 ,3
,XUE Jin‐
y
un
1 ,3
(1 .College of Computer Information Engineering ,Jiangxi Normal University ,Nanchang
330027 ,China ;2 .Computing Centre ,Nanchang University ,Nanchang
330029 ,China ;3 .Key Laboratory for Computer Science ,Institute of
Software ,Chinese Academy of Science ,Beijing 100080 ,China)
Abstract : The temporal logic is a formal method for describing sequences of transition between states
in a reactive (concurrent) system .It is common to use the temporal logic to specify the properties that
the design must satisfy .The temporal logic is the basic of model checking .This paper states the syn‐
tax and semantics of CTL
倡
and its sub‐logics :CTL and LTL ,and analyzes how to state the properties
of concurrent system ,and finally the application example is given .
Key words : formal method ;concurrent system ;temporal logic ;model checking
形式化方法是提高软件系统 ,特别是 safety‐critical 系统安全性与可靠性的重要手段
[1]
.在为此提
出的诸多形式化方法中 ,模型检测以其简洁明了和自动化程度高而引人注目
[2]
.直观地讲 ,一个并发系
统就是一个运行在多机或支持多进程的单机体系结构上的软件系统 ,一个并发程序的执行序列是由交
错的两个或多个(可并发执行的)进程组成的状态变换序列 .时态逻辑(temporal logics)
[3 ~ 5]
是一种描述
反应式(并发)系统中状态迁移序列的形式化方法 ,时态逻辑是模型检测的基础 ,用以描述并发系统的性
质 ,不同的时态逻辑有其相应的(时态/模态)算子及其对应的语义 .
1 时态逻辑
由于并发执行的程序在执行过程中各程序交替点具有不确定性 ,导致对各程序的走停点及交替过
程也具有不确定性 ,使得并发程序的描述与时间变化密切相关 .在时态逻辑中 ,时间并不是显式地表述 ,
第 16 卷 第 5 期
2004 年 10 月
海 军 工 程 大 学 学 报
JOURNAL OF NAVAL UNIVERSITY OF ENGINEERING
Vol .16 No .5
Oct .2004
倡
收稿日期 :2004‐05‐15 ;修订日期 :2004‐06‐08
基金项目 :国家自然科学基金资助项目(60273092) ;江西省自然科学基金资助项目 (0411041) ;南昌大学 2003 年
度科研基金资助项目
作者简介 :肖美华(1967‐) ,男 ,副教授 ,博士生 .