XYZ／SE程序的验证

ＸＹＺ／Ｅ的好处之一在于高级和低级的说明能够在同一框架下表示，因而使得软件的说明和实现变得容易一些．在这同时，开发验证工具以验证不同层次的说明是否满足所期望的关系是很重要的．谢洪亮等同志曾研究过ＸＹＺ／ＳＥ程序的验证规则．本篇文章增加了有关使用数组、过程说明和过程调用的规则．同时着重说明ＸＹＺ／ＳＥ程序验证的自动化方面的问题，且实现了一些化简验证条件的规则．     

UML2．0顺序图的XYZ／E时序逻辑语义研究

UML2．0顺序图适合于描述软件体系结构的各个组件之间和复合组件内部各个子组件之间的动态交互行为，但由于UML2．0顺序图的语义不够精确，使得它的描述结果不利于进一步的分析和验证。基于此，本文在定义UML2．0顺序图的语法和语法约束的基础上，给出了UML2．0顺序图的XYZ／E时序逻辑语义，为使用UML2．0顺序图与XYZ／E相结合的方式来描述软件体系结构的动态交互行为奠定了基础。     

混合投影时序逻辑与混合系统的形式化验证

为了描述混合系统的性质和行为，10多年来，各种时序逻辑，如Hybrid Temporal Logic等相继出现。这些时序逻辑适用于刻画混合系统的性质和规范，但不适宜表示描述系统的实现模型。本文定义了一个混合投影时序逻辑（Hybrid Projection Temporal Logic，简称HPTL），既能刻画混合系统的性质，又能表示混合系统的实现。这样，混合系统的验证就可以很方便地在统一的数学模型框架下进行。同时，给出了HPTL的基本的逻辑等价式系统和一个用HPTL进行混合系统验证的实例。     

基于时序Petri网的联锁逻辑形式建模与验证

时序Petri网结合Petri和时序逻辑的优点,清晰简洁地描述并发系统事件间的时序和因果关系,包括系统的最终性和公平性。文章给出安全苛求系统——车站信号联锁逻辑系统的时序Petri网描述,并使用时序逻辑描述系统状态的时序和因果关系,最后通过分析和验证模型的性质得出系统是正确的。     

反应系统的连续时序逻辑表示和验证

引进一个称为LTLC的连续时间时序逻辑，用来对反应系统进行规范与验证．LTLC的一个重要特点是它能在统一的逻辑框架下表示反应系统及其性质，这样就可将系统与性质问的满足关系转化为逻辑公式间的蕴涵关系．同时，采用非负实数集作为时间域还使我们可以利用标准的存在量词来表示变量隐藏，并可用逻辑蕴涵来表示反应系统间的求精关系．该文首先给出了LTLC的一个简单介绍，然后讨论了如何使用LTLC对反应系统进行表示与推理，最后证明了一个关于LTLC的可判定性结果．此结果可用于有穷状态反应系统的自动验证．     

基于时序逻辑软件构架形式化方法研究

随着软件系统的规模和复杂性日益增加,人们已经超越传统的“算法+数据结构=程序”的软件设计模式,软件系统的整体结构,即软件构架(Software Architecture)成为软件设计的重心和难点。运用形式化方法描述大规模、复杂软件系统的构架,能够阐明软件系统的真实内涵,有助于系统设计人员和相关人员更准确地了解系统,达成共识,避免误解。但更重要的是,形式化描述软件构架奠定了利用数学方法对软件构     

实时系统的形式化验证

实时系统的设计对系统设计人员而言是一个巨大挑战。在缺乏严格的验证环境时 ,要避免设计错误是很困难的。本文将一种带时戳的时序逻辑及用于描述具体实时系统的时间变迁系统编码到 HOL定理证明器中 ,并实现了一个基本的规则策略库 ,从而实现了一个简单的交互式辅助验证环境L RP。实例 Fisher算法的互斥性在 IRP中得到了验证。     

行为时序逻辑与自反线性时序逻辑的关系

为了能够将哲学逻辑中的公理系统运用到行为时序逻辑的研究中。对行为时序逻辑公式的语义进行形式化定义．从语义和语法两方面研究行为时序逻辑公理系统和具有自反性质的线性时序逻辑公理系统之间的联系．提出并证明行为时序逻辑公式转换为自反线性时序逻辑公式的定理。按照集合论和模型论的思想,定义行为时序逻辑中项和行为时序逻辑原子公式的概念。定义Lesilie Lamport所提出的行为时序逻辑公式的语义。证明自反线性时序逻辑公理系统适用于行为时序逻辑公理系统．以此为基础证明行为时序逻辑的简单规则、基本规则和附加规则。     

XYZ／CFC与XYZ／PAD：图形一文本程序设计环境

ＸＹＺ系统是一个ＣＡＳＥ工具系统．它的核心是一个时序逻辑语言ＸＹＺ／Ｅ．ＸＹＺ／Ｅ有一基本的表示状态转换的低级形式ＸＹＺ／ＢＥ（或用于表示并发的ＸＹＺ／ＣＥ）及一个结构化的高级形式ＸＹＺ／ＳＥ．它们均有其相应的图形表示．ＸＹＺ／ＣＦＣ与ＸＹＺ／ＰＡＤ是分别以ＸＹＺ／ＢＥ（或ＸＹＺ／ＣＥ）及ＸＹＺ／ＳＥ用逐步求精方法进行程序设计的交互式的图形环境．每步均可由图形程序自动生成时序逻辑形式的程序．     

时态逻辑与程序验证

近年来,时态逻辑大量应用于程序验证,采取的途径随使用的时态逻辑的形式和方法的不同而异。本文用自动机理论研究几种时态逻辑(LTL,BTL,POTL)的模型和模型生成子,并讨论用时态逻辑进行程序验证的的重要途径。     

时序逻辑程序的模型检测

时序逻辑程序的形式化验证对提高程序的正确性具有重要意义。以投影时序逻辑的可执行子集、框架投影时序逻辑语言Framed Tempura为研究对象,使用命题投影时序逻辑描述Framed Tempura程序的性质,将程序p和性质Ф统一表示在投影时序逻辑中,模型检测需要判定p→Ф是否有效,可转化为判定p∧Ф是否不可满足,这可以通过构造p∧Ф的正则图加以解决。最后,给出了Framed Tempura程序的模型检测实例。     

用XYZ／E语言描述和验证硬件的行为

本文考虑用时态逻辑语言ＸＹＺ／Ｅ描述硬件行为的可行性．作为实例，用ＸＹＺ／Ｅ语言描述了一个基于微处理器的容错计算机系统，这种描述可以在ＸＹＺ系统上执行，从而可对系统进行模拟．特别有意义的是利用ＸＹＺ／ＶＥＲＩ验证子系统对所期望的性质进行了形式化证明．本文还将ＸＹＺ／Ｅ描述与相应的ＶＨＤＬ（ＶＨＳＩＣｈａｒｄｗａｒｅｄｅｓｃｒｉｐｔｉｏｎｌａｎｇｕａｇｅ）描述进行了比较．从中可以看出时态逻辑语言的描述具有其独特的优点.     

一种用于指针程序安全性证明的指针逻辑

在高可信软件的各种性质中,安全性是被关注的重点,其中软件满足安全策略的证明方法是研究的热点之一.文中根据作者所设想的安全程序的设计和证明框架,为类C语言的一个子集设计了一个指针逻辑系统.该逻辑系统是Hoare逻辑系统的一种扩展,它用推理规则来表达每一种语句引起指针信息的变化情况.它可用来对指针程序进行精确的指针分析,所获得的信息用来证明指针程序是否满足定型规则的附加条件,以支持程序的安全性验证.该逻辑系统也可用来证明指针程序的其它性质.     

基于XYZ/E的混成系统

混成系统是由计算机和物理设备组成的嵌入式实时计算系统.它允许在交互式实时系统中引入连续变化的单元.XYZ/E 是基于Manna-Pnueli的线性时序逻辑的程序设计语言.它将程序的动态语义与静态语义统一在同一框架中,支持从抽象的程序规范到可执行代码的逐步求精的全过程.该文使用XYZ/E语言描述和验证混成系统.首先介绍了计算模型,然后介绍了XYZ语言对混成系统的形式化描述,最后介绍了混成系统的验证.与同类工作相比,XYZ/E支持状态转换,从而可以方便地描述复杂的控制算法.     

一种用于指针程序验证的指针逻辑

本文改进并扩展先前为验证指针程序提出的指针逻辑,主要贡献是提出了合法访问路径集合的概念,极大地简化了访问路径上的基本运算,并使得指针逻辑推理规则变得易理解.另外,增加了局部推理规则和函数构造的推理规则,使得指针逻辑可以方便地用于有函数调用的场合.     

步进索引模型下的语义及其形式化

霍尔逻辑作为计算机程序的逻辑基础,可以用于描述一般程序的验证.分离逻辑作为霍尔逻辑的扩展,可以支持很多现代程序语言中的高阶特性.步进索引模型被用于定义自递归谓词.步进索引逻辑被广泛应用于各种基于交互式定理证明器的程序验证工具中,然而,基于步进索引逻辑的推理却比经典逻辑复杂、繁琐.事实上,也可以在步进索引模型上定义更加简洁清晰的、与“步数”无关的经典逻辑体系下的非步进索引程序语义.人们希望找到步进索引逻辑和非步进索引逻辑之间的关系,但发现两种逻辑并不等价.对实际的程序验证工作中涉及的命题进行归纳总结,找出它们共同的特征,给出关于程序状态的断言的约束条件;分别定义步进索引逻辑和非步进索引逻辑体系中断言的语义,并证明在该约束条件下两种语义的等价性;在Coq中,形式化以上所有定义和证明;最后,对未来值得关注的研究方向进行初步探讨.     

扩充析取逻辑程序的争论语义

该文探讨争论推理在扩充逻辑程序中的实现及其关系问题.基于“相干原理”,建立了扩充逻辑程序的争论推理框架,多种争论推理形式都可以嵌入其中.特别是提出了一种谨慎语义Acc.同时又定义了良基语义的一种合理扩充Mod,以处理较为大胆的推理形式.另外也研究了相关的理论性质.