面向对象的时序逻辑语言

针对时序逻辑语言缺少面向对象概念的现状,对投影时序逻辑进行了扩展,介绍了新的语法和语义。在扩展投影时序逻辑中,基于变量集合的层次化和谓词的分组,给出了对象、类和继承等概念的形式化定义。扩展投影时序逻辑的一个可执行子集被定义为面向对象的时序逻辑语言Framed Tempura++,它能够用于面向对象的程序设计,可以模拟组合Web服务的执行。所给出的实例表明,该语言与Framed Tempura相比,能有效地重用代码,提高了代码的可读性和可维护性。     

自由选择工作流网的可靠完备化简规则集

流程化简技术是一种重要的商业流程模型分析方法.已有的非形式化化简方法因缺乏理论基础而无法保证完备性.基于Petri 网的化简方法应用范围不针对流程模型因而不能保证可靠性.提出了针对自由选择工作流网的一个可靠完备化简规则集,可靠性保证化简过程中这类模型的行为正确性被保持,完备性保证任意一个正确的此类工作流网最终都能被化简为最简形式.基于化简规则集给出可靠完备的合成规则集,用于流程模型的设计与精化.     

分布式软件系统交互行为建模、验证与测试

为了确保分析与设计阶段分布式软件系统中模块之间交互行为的正确性,提出了一种分布式软件系统模块交互的抽象方法,分别通过系统状态机图和对象状态机图对各模块状态变迁进行建模,使用UML2．0序列图对模块之间交互行为进行描述．采用基于命题投影时序逻辑的模型检测技术,将对象状态机图转换为 Promela 模型,系统交互性质转换为命题投影时序逻辑公式,通过模型检测器验证交互模型是否满足于系统的性质,若不满足于该性质,则能够获得反例执行的路径．给出了一个分布式软件系统测试框架,在验证后的序列图模型基础上,使用基于模型的测试用例自动生成方法得到测试用例集合,该集合能够实现对交互行为的有效测试．实例结果表明,该方法可以提高分布式软件系统中模块交互行为的有效性和可靠性．     

BPEL 流程建模中的交叠模式分析与转换

由图形化流程建模语言生成可执行的业务流程语言(business process execution language,简称BPEL)时,对于源模型中顺序与并发结构交织的情况(称为交叠模式),传统的复制相关活动方法缺少系统分析及形式化描述.针对这一现状,提出基于工作流网的UML活动图生成BPEL方法,以自由选择工作流网作为活动图的理论基础,利用活的、有界的自由选择网系统的合成规则,定义合理的自由选择工作流网中的两种交叠模式,针对其中一种给出复制相关活动的形式化转换方法,并借助Petri网的并发正则表达式证明转换等价性,说明另一种交叠模式中复制相关活动方法的适用范围.针对BPEL流程建模及图形化流程语言生成块状语言过程中的交叠模式转换问题,给出形式化的描述与解决方法.     

进位保留加法器的命题投影时序逻辑组合验证

为保证硬件设计的正确性,提出了对硬件设计组合验证的新方法．该方法在命题投影时序逻辑的统一框架下,实现对硬件系统行为的建模,对所期望性质的形式化描述,并利用命题投影时序逻辑合理且完备的公理系统对系统性质进行验证,从而证明硬件系统满足期望的性质,保证设计的正确性．进位保留加法器的验证实例说明了该方法的可行性．     

支持Stutter-不变性的命题区间时序逻辑

为了将命题区间时序逻辑(PITL)应用于组合验证,并降低组合产生的状态爆炸风险,提出了支持Stutter-不变性的命题区间时序逻辑PITLst.PITLst继承了PITL的结构相关性,可表达所有PITL能够表达的Stutter-不变性质,支持模块抽象约简系统规模,降低了状态爆炸风险.自动加油站模型的组合验证实例表明,PITLst可有效应用于组合验证技术.     

Streett自动机确定化工具

自动机的确定化是将非确定性自动机转换为接收相同语言的确定性自动机,是自动机理论的基本问题之一.ω自动机的确定化是诸多逻辑,如SnS, CTL*,μ演算等,判定过程的基础,同时也是解决无限博弈求解问题的关键,因此对ω自动机确定化的研究具有重要意义.主要关注一类ω自动机——Streett自动机的确定化.非确定性Streett自动机可以转换为等价的确定性Rabin或Parity自动机,在前期工作中已经分别得到了状态复杂度最优以及渐进最优算法,为了验证提出的算法的实际效果,也为了形象地展示确定化过程,开发一款支持Streett自动机确定化的工具是必要的.首先介绍4种不同的Streett确定化结构:μ-Safra tree和H-Safra tree (最优)将Streett确定化为Rabin自动机, compact Streett Safra tree和LIR-H-Safra tree (渐进最优)将Streett确定化为Parity自动机;然后,根据Streett确定化算法,基于开源工具GOAL (graphical tool for omega-automata and logics),实现...     

用于验证多智能体系统的APTL模型检测器

由于经典的线性时序逻辑表达能力有限,设计并开发了基于交替投影时序逻辑（alternating projection temporal logic,简称APTL）的模型检测工具.根据王海洋等人提出的APTL符号模型检测方法,设计并实现了APTL模型检测器MCMAS_APTL.该工具可用于多智能体系统（multi-agent system,简称MAS）的性质验证.MCMAS_APTL检查MAS是否满足具体性质的过程如下：首先,用解释系统编程语言（interpreted system programming language,简称ISPL）描述要验证的系统IS,用APTL公式P描述要验证的性质;然后,符号化表示系统IS,并将非P转化为范式;最后,计算所有满足非P的路径的起始状态集合.如果得到的状态集合中包含系统的初始状态,则说明系统不满足公式P;反之,则说明系统满足公式P.详细阐述了实现MCMAS_APTL的过程,并且通过验证机器人足球赛的例子展示了MCMAS_APTL的性能.     

APTL公式的可满足性检查工具

交替投影时序逻辑（Alternating Projection Temporal Logic,简称APTL）公式简单易懂,表达能力强;不仅可以描述经典时序逻辑LTL可以描述的性质,而且可以描述与区间相关的顺序和循环性质以及开放系统和多智能体系统中与博弈相关的性质.在验证系统是否满足所给的APTL公式所描述的性质之前需要检查公式的可满足性.本文根据检查APTL公式的可满足性的方法^[1],开发实现了工具APTL2BCG.具体细节如下：首先,利用公式P的范式构造P的标记范式图（Labeled Normal Form Graph,简称LNFG）;然后,将LNFG转化为广义的基于并发博弈结构的交替Büchi自动机（Generalized alternating Büchi automaton over Concurrent Game structure,简称GBCG）;最后,将GBCG转化为基于并发博弈结构的交替Büchi自动机（alternating Büchi automaton over Concurrent Game structure,简称BCG）并且化为最简形式并检查公式P的可满足性.     

Einstein谜的SAT求解

Einstein谜,亦称Zebra谜,是爱因斯坦在20世纪初提出的,他说世界上有98%的人答不出来。该问题是一个典型的逻辑推理题,可以通过SAT求解给出问题的答案。现将Einstein谜转换成SAT求解问题,并使用当前流行的SAT求解器,如MinSat,对Einstein谜进行自动求解。