操作系统微内核技术研究*

文章介绍了作者在过去5年中在微内核技术上所做的工作.给出了3个算法.① 通过将任务调度和线程调度算法相结合的方法，来解决单纯以线程为单位的调度系统的效率和公平性问题；② 一个改进的写时拷贝算法，它结合写时拷贝算法和访问时拷贝算法的优点，来解决写时拷贝算法在I386体系结构上的适应性问题；③ 提出了一个微内核操作系统计时模型，它解决了传统计时算法在微内核系统中计时不准确的问题.     

基于KAP有向图模型的医学图像分类算法*

脑部CT图像拥有良好的纹理特性且图像间纹理角点的位置近似相同。基于此原因,文中提出基于K最近邻纹理角点(KAP)有向图模型的医学图像分类算法。首先提出面向纹理的角点提取方法;然后针对提取的角点,结合医学图像的固有特点,提出KAP有向图模型用于描述医学图像;最后基于KAP有向图模型提出医学图像分类算法。实验表明,文中算法在时间复杂度和准确度方面都取得较好结果。     

对象的RSBO表示模型*

对象的内部表示决定了对象的存储方式和访问方式,文章介绍了RSBO(refined synchronous buffers of objects)表示方法,是SBO(synchronous buffers of objects)对象表示法的改进.RSBO表示法利用解析对象结构方式,把对象的复杂结构分解为具有相对简单结构的对象节.RSBO在SBO表示法的基础上引入了指针节的机制.指针节结构是对象指针的扩展,并能同时支持在复杂对象的集合上的访问和计算.另外介绍了基于RSBO对象的访问方式和索引结构,传统数据库中     

刻画基于模型的中心诊断*

虽然对基于模型的诊断存在一系列不同的逻辑定义,但所幸的是存在一个统一的抽象定义,它概括了以往的不同定义.在该定义基础上提出了基于模型的中心诊断的概念.通过刻画基于模型的中心诊断过程,论证了基于模型的中心诊断与本原蕴含/蕴含式的直接关系,从而将其理论结果与ATMS(assumption-based truth maintenance system)这类算法联系起来.进一步指出,对基于一致性中心诊断的刻画仅仅是文中所给出的刻画的一个特殊情形.     

对象形式语义模型*

在面向对象的软件构造中，对象被视为软件系统的基本构件本文给出一个对象形式语义模型，对象被定义为封装属性和行为的实体，对象行为必须满足给定的静态约束和时序约束；基于对象态射，本文给出对象聚合、特化、继承和对象类等概念在此语义模型框架中的解释。     

群组通信模型及运输协议映射*

新型网络应用要求通信协议提供多点投递和相应群组管理功能,同时,高速传输服务和新型网络层协议也开始具有数据多点传输和简单群组控制能力,跨越两者的运输层协议,从而又重新成为学术研究和标准化的热点和趋势.文章主要描述建立群组通信抽象模型的过程和结论以及参照新型运输协议XTP(express transport protocol)和计算机会议应用的模型映射和评价.     

复杂对象数据库的递归查询语义*

本文用代数规范方法定义了复杂对象数据库中的对象标识、对象值、查询谓词和数据库状态语义，通过对查询路径的分析，给出了个体对象查询条件匹配的语义，特别是在个体对象上施用递归查询的语义．最后，给出了OODB中选择操作的语义．     

模型库管理系统的设计和实现*

模型库管理系统是决策支持系统的核心，其基本功能包括模型的定义、组合、存储和调用.该文介绍一个支持客户/服务器模式的模型库管理系统的设计和实现，在这个系统中，模型被视为程序模块，通过运用面向对象的方法进行组织以及对模型的远程和动态的透明调用提供支持，使实现的系统具有良好的动态可扩充性.同时,通过提供模型定义语言和模型库管理，便于决策支持系统客户软件的开发.     

管理信息系统中的面向对象体系模型*

本文采用面向对象的思想提出了描述管理信息系统(MIS)的一种体系模型，给出了在软件开发过程中如何获取体系模型中各组成部分的准则和方法，并应用于实际开发项目中．     

具有过去时态算子的计算树逻辑模型检测

在计算树逻辑(CTL)中引入过去时态算子,得到了表达力更强的属性规约语言CTLP,给出了CTLP 的模型检测算法及其固定点刻画.该算法的复杂性和CTL一样.固定点刻画使得CTLP的符号模型检测过程能够实现,从而有效克服了模型检测中的状态爆炸问题.     

基于时态测试器的实时分支时态逻辑模型检测

基于自动机理论的模型检测技术在形式化验证领域处于核心地位, 然而传统自动机在时态算子上不具备可组合性, 导致各种时态逻辑的模型检测算法不能有机整合.本文为了实现集成限界时态算子的实时分支时态逻辑RTCTL*的高效模型检测, 提出一种RTCTL*正时态测试器构造方法, 以及相关符号化模型检测算法.证明了所提出的RTCTL*正时态测试器构造方法是完备的.也证明了该算法时间复杂度与被验证系统呈线性关系, 与公式长度呈指数关系.我们基于JavaBDD软件包成功开发了该算法的模型检测工具MCTK 2.0.0.我们完成了MCTK与著名的符号化模型检测工具nuXmv之间的实验对比分析工作, 结果表明MCTK虽然在内存消耗上要多于nuXmv, 但是MCTK的时间复杂度双指数级小于nuXmv, 使得利用MCTK验证大规模系统的实时时态性质成为可能.     

基于模型检验的构件验证技术研究进展

模型检验以其自动化程度和完备性高、与构件技术互补性强等特点,在软件构件可信性质的分析和验证中发挥着日益重要的作用.将基于模型检验的构件验证方法分为基于系统规约模型的验证和基于源代码的验证,分别对其研究现状和发展动态进行了详细的综合评述.首先对模型检验与构件可信性质验证的关系进行了探讨,接着对基于SOFA,Fractal,CORBA及各种特定构件模型的验证方法和基于转化思想的源码验证、面向源码的直接验证及面向可执行代码的动态验证方法分别进行了评述.最后,指出了基于模型检验的构件验证技术所面临的主要挑战和未来的发展方向.     

基于符号模型检测的Web服务组合形式化验证

随着经济的发展和市场竞争的加剧,企业必须能够快速且准确地满足市场和用户的各种需求.Web服务组合正是由于单个Web服务不能满足企业及用户的需求而产生的一种技术,而如何确保组合的正确性来实现服务增值是一个尚未完全解决的问题.针对此问题,提出了一种基于符号模型检测器NuSMV对Web服务组合进行验证的方法,并提出了基于消息...     

Bounded Model Checking of CTL

Bounded Model Checking has been recently introduced as an efficient verification method for reactive systems. This technique reduces model checking of linear temporal logic to propositional satisfiability. In this paper we first present how quantified Boolean decision procedures can replace BDDs. We introduce a bounded model checking procedure for temporal logic CTL＊ which reduces model checking to the satisfiability of quantified Boolean formulas. Our new technique avoids the space blow up of BDDs, and extends the concept of bounded model checking.     

基于电路拓扑结构分析的等价性验证方法

随着集成电路设计规模的日益增大,结合多种推理引擎已成为组合电路形式化等价性验证的重要手段.提出一种基于电路拓扑结构分析的组合等价性验证方法,将电路的拓扑结构与验证算法的复杂性关联起来.在验证过程开始之前,利用min-cut方法计算表征电路复杂性的"电路宽度",以确定最佳的推理引擎,避免了传统的引擎切换过程,提高了算法的效率.针对ISCAS85电路的实验结果表明了该方法的效率和可行性.     

Another Look at LTL Model Checking

We show how LTL model checking can be reduced to CTL model checking with fairness constraints. Using this reduction, we also describe how to construct a symbolic LTL model checker that appears to be quite efficient in practice. In particular, we show how the SMV model checking system developed by McMillan [16] can be extended to permit LTL specifications. The results that we have obtained are quite surprising. For the specifications which can be expressed in both CTL and LTL, the LTL model checker required at most twice as much time and space as the CTL model checker. We also succeeded in verifying non-trivial LTL specifications. The amount of time and space that is required is quite reasonable. Based on the examples that we considered, it appears that efficient LTL model checking is possible when the specifications are not excessively complicated.