面向传值进程的谓词μ-演算与FO(HML)的完备推演系统

作者提出一个谓词μ－演算系统，目的在于描述传值进程的性质，该系统的公式和谓词相互递归定义，谓词中含有抽象式，谓词变元以及最大和最小不动点，其语义模型是带赋值的符号迁移图所诱导的迁移系统，并且该系统包含Hennessy-Milner逻辑的一阶扩弃FO（HML）作为子系统，作者用例说明了本演算系统在表达传值进程性质方面的优越性，该文后半部分主要给出了FO（HML）的一个推演系统，并运用判定树（Tableau)的方法，证明了所给出了推演系统是完备的。     

时间符号迁移图及其互模拟判定

引入时间符号迁移图的概念，作为既涉及通讯又具有实时性的并发系统的模型，该文给出了这种迁移图时间互模拟的算法，并证明了该算法的正确性。     

谓词μ演算和模态图的语义一致性

模态图是谓词μ演算的一种有效的图形表示形式.证明了谓词μ演算和模态图的语义一致性,详细讨论了谓词μ演算公式、嵌套谓词等式系和模态图之间的关系,并给出了一种优化的从线性公式到嵌套谓词等式系的转换算法.     

一种基于时间自动机的实时系统测试方法

基于时间自动机(timed automata,简称TA)的一种变体--时间安全输入/输出自动机(timed safety input/output automata,简称TSIOA),提出了一种实时系统测试方法.该方法首先将时间安全输入/输出自动机描述的系统模型转换为不含抽象时间延迟迁移的稳定符号状态迁移图(untimed stable transition graph of symbolic state,简称USTGSS);然后采用基于标号迁移系统(labeled transition system,简称LTS)的测试方法来静态生成满足各种结构覆盖标准的包含时间延迟变量迁移动作序列;最后,给出了一个根据迁移动作序列构造和执行测试用例的过程,该过程引入了时间延迟变量目标函数,并采用线性约束求解方法动态求解迁移动作序列中的时间延迟变量.     

基于谓词切片的字符串测试数据自动生成

字符串谓词使用相当普遍，如何实现字符串测试数据的自动生成是一个有待解决的问题，针对字符串谓词，讨论了路径Path上给定谓词的谓词切片的动态生成算法，以及基于谓词切片的字符串测试数据自动生成方法，并给出了字符串间距离的定义，利用程序DUC（Definithon-Use-Control)表达式，构造谓词的谓词切片，对任意的输入，通过执行谓词切片，获取谓词中变量的当前值，进而对谓词中变量的每一字符进行分支函数极小化，动态生成给定字符串谓词边界的ON－OFF测试点，实验表明，该方法是行之有效的。     

基于类型化Pi-演算的Web服务组合相容性检测

定义了一个Pi-演算的类型系统，然后利用扩充后的类型化Pi-演算建模BPEIAWS描述的Web服务组合系统。提出了基于类型化Pi-演算的服务组合相容性检测算法。并给出了一个银行贷款审批系统检测实例的片段，说明利用该算法检测服务组合系统相容性的可行性。     

基于符号迁移图的互模拟验证算法

符号迁移图是传值进程的一种直观而简洁的语义表示模型，该模型由Hennessy和Lin首先提出，随后又被Lin推广至带赋值的符号迁移图，本文不但定义了符号迁移图各种版本（基／符号）的强操作语义和强互模拟，提出了相互的强互模拟算法，而且通过引入符号观察图和符号同余图，给出了其弱互模拟等价和观察同余的验证算法，给出并证明了了τ－循环和τ－边消去定理，在应用任何弱互模拟观察同余验证算法之前，均可利用这些定理对所给符号迁移图进行化简。     

基于符号模型检测的符号有向图故障诊断解形式化验证

由于定量信息和非线性因果关系的丢失,符号有向图(SDG)的故障诊断解需要进一步进行校核与验证.将SDG故障诊断解的验证置于符号模型检测框架中进行研究,提出了基于符号模型检测的SDG故障诊断解形式化验证方法.首先定义了SDG模型的有限状态变迁系统形式化描述,建立了符号模型检测(SMV)模型;其次引入故障传播时间定义了模型观测变量的动态验证信息,提出了基于步进式监控的动态推理验证策略;然后扩展了动态推理验证过程的SMV模型,提出了验证算法SSDGFD_SMC;最后,通过一个简单贮水罐系统的SDG模型实例验证了算法SSDGFD_SMC的有效性.     

半边图模型之构造演算

提出一个动态可增殖的多层次自组织认知系统,每个层次具有形式上一致的知识表示方法,各层的自组关联、自组聚合、归约和样本表达四个知识处理模型是实现系统自组织层次增殖的核心模型。指出若要实现层次可自组织增殖的系统,其关键是要设计一个合理的聚合归约演算系统;提出一个适用于各个层次的基于可结合半边的自组图知识表示法,先给出自组图形式化的静态定义和动态定义,然后以自组关联模型为背景给出对应的自组图构造算法。     

嵌套谓词等式系与弱互模拟

带赋值符号迁移图是一般传值进程的语义模型,其强互模拟等价可以归结为谓词等式系的最大解.该文将这一结果推广到弱互模拟等价,为此,引入嵌套谓词等式系的概念,并提出算法,将带赋值符号迁移图的弱互模拟等价归结为形如E₂μE₁的嵌套谓词等式系的最大解.     

路由协议的符号化测试生成

协议一致性测试用于验证协议实现的正确性.文中根据路由协议的消息复杂特点,提出基于on-the-fly策略符号测试生成与动态执行的算法:建立了一种新的统一符号语义模型,该模型把数据操作和控制都抽象为动作行为;以该语义模型为基础,扩展了行为之间的关系以及一致性测试关系;给出了基于on-the-fly策略符号测试生成与符号动态执行的算法,在符号动态执行中,使用了统计的聚类算法来进行符号的数据选择.论文最后用具体的测试例说明该算法在OSPFv3协议一致性测试上的应用.     

基于π演算的工作流模型检验

为保证工作流模型语义的正确性,提出一种基于π演算的工作流模型语义性质检验方法。采用π演算的一个子集πN演算描述工作流模型,证明该模型的反应关系能够终止,构造有限反应迁移图算法,利用NuSMV检验工作流模型是否满足线性时序逻辑性质。实验结果证明了该检验方法的有效性。     

基于符号模型检测的SDG故障诊断解形式化验证

由于定量信息和非线性因果关系的丢失,SDG的故障诊断解需要进一步的进行校核与验证。创新地将SDG故障诊断解的验证置于符号模型检测框架中进行研究,提出了基于符号模型检测的SDG故障诊断形式化验证方法。首先扩展、转换了SDG模型的有限状态变迁系统形式化描述,建立了SMV模型;其次引入故障传播时间建立了模型观测变量的动态验证信息,并基于步进式监控分析了动态验证策略,将SDG正向推理扩展建模为动态推理验证;然后面向符号模型检测扩展了动态推理验证过程的SMV模型,提出了验证算法SSDGFD_ SMC;最后,通过一个实例验证了算法的有效性。     

命题μ-演算局部模型检测高效算法设计

命题μ-演算局部模型检测算法中,目前最好的算法的时间复杂度与不动点算子交替嵌套深度d呈指数关系。针对命题μ-演算局部模型检测算法的计算过程进行分析,得到迭代计算的中间迭代值间满足的一组偏序关系,然后利用该偏序关系设计了一个局部模型检测算法,算法时间复杂度的指数部分为d/2,大大提高了算法的计算效率。     

基于时间自动机的测试用例自动生成及执行方法

为了实现对时间自动机模型的测试,采用符号状态拆分算法对时间自动机的状态空间进行等价划分,以得到最简稳定符号状态转移图,并将其中的抽象时间延迟转移替换为时间延迟变量;针对系统中每个时间自动机建立各自的符号状态转移图,再采用基于符号迁移系统的测试方法分别生成相应的转移动作序列;最后通过对这些序列进行组合产生系统的测试用例,为了执行测试用例,利用TTCN-3的多PTC并发执行能力来实施测试.     

一种网格环境下的动态故障检测算法

针对现有网格系统出错几率较大、已有故障检测算法不能有效满足网格系统需求问题，提出了一种网格环境下的动态故障检测算法．根据网格系统的特点，基于不可靠故障检测思想，建立了网格系统模型和故障检测模型；结合心跳（heartbeat）策略和灰色预测方法，设计了一种动态心跳机制，并给出了预测模型和实时预测策略；提出了基于该动态心跳机制的网格故障检测算法，分析了算法的可靠性．仿真实验结果表明，该算法是正确、有效的，可用于网格环境下的故障检测．     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。     

动态随机影响图建模方法

通过引入时间片的概念和反馈特性,时间片影响图增强了经典影响图描述因果影响关系网络的能力,但仍不足以支撑对复杂系统/体系问题中并发、交互、协同等过程的有效描述.参考离散事件系统建模的相关特性及方法,通过增加一个时间变量节点并扩展现有的模型规范,提出了一种动态随机影响图建模方法;详细说明了该方法的图形化语法、语义,并给出了其模型节点逻辑关系的迭代演算算法.该方法较完整地保持了典型时间片影响图的现有特性,可以作为改进现有方法的折中方案,以描述决策问题中的复杂行为过程.     

STGA的变种及其互模拟验证

为刻画和验证无穷值域上的传值进程，Ｈｅｎｎｅｓｓｙ和Ｌｉｎ先后提出符号迁移图（ＳＴＧ）和带赋值符号迁移图（ＳＴＧＡ）作为传值进程的语义表示模型，并给出了相应的强互模拟算法．为将该方法推广至实际应用中更常用的弱互模拟等价和观察同余的验证问题，该文首先引入了ＳＴＧＡ的一个变种，它与原模型的不同之处在于将符号迁移上赋值和符号动作的执行次序颠倒，因而可定义些种ＳＴＧＡ结果间的符号双迁移关系．文中提出了从正     

一种面向高动态范围材质的实时渲染算法

针对具有高动态范围材质的场景的渲染问题，给出了将渲染光照模型由传统材质模型扩展为高动态范围材质模型和基于GPU实时渲染的算法。经过此算法得到的高动态范围渲染结果必须通过进一步的处理才能正确地显示在仅具有低动态范围的显示输出设备上。为此，该文给出了一个结合高动态范围材质的实时渲染算法、基于物理的模拟镜头眩光效果算法以及色调映射算法的综合方法，并通过实现验证了此方法。