基于线性时序逻辑的实时系统模型检查

模型检查是一种用于并发系统的性质验证的算法技术.LTLC(linear temporal logic with clocks)是一种连续时间时序逻辑,它是线性时序逻辑LTL的一种实时扩充.讨论实时系统关于LTLC公式的模型检查问题,将实时系统关于LTLC公式的模型检查化归为有穷状态转换系统关于LTL公式的模型检查,从而可以利用LTL的模型检查工具来对LTLC进行模型检查.由于LTLC既能表示实时系统的性质,又能表示实时系统的实现,这就使得时序逻辑LTLC的模型检查过程既能用于实时系统的性质验证,又能用于实时系统之间的一致性验证.     

带有时钟变量的线性时序逻辑与实时系统验证

为了描述实时系统的性质和行为,10多年来,各种不同的时序逻辑,如Timed Computation Tree Logic,Metric Interval Temporal Logic和Real-Time Temporal Logic等相继提出来.这些时序逻辑适于表示实时系统的性质和规范,但不适于表示实时系统的实现模型.这样,在基于时序逻辑的实时系统的研究中,系统的性质和实现通常是用两种不同的语言来表示的.定义了一个带有时钟变量的线性时序逻辑(linear temporal logic with clocks,简称LTLC).它是由Manna和Pnueli提出的线性时序逻辑在实时情况下的一个推广.LTLC既能表示实时系统的性质,又能很方便地表示实时系统的实现.它能在统一的语义框架中表示出从高级的需求规范到低级的实现模型之间的不同抽象层次上的系统描述,并且能用逻辑蕴涵来表示不同抽象层次的系统描述之间的语义一致性.LTLC的这个特点将有助于实时系统的性质验证和实时系统的逐步求精.     

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

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

基于时序逻辑语言描述的监控系统的软件体系结构求精

该文提出了一种基于组件的软件体系结构求精方法,主要通过一个具体实例———移动通信监控系统,基于时序逻辑语言XYZ/E形式化描述其体系结构,对该求精方法及过程做进一步阐述。     

基于线性时序逻辑的多Agent协商推理模型

在多智能体系统中,协商是Agent交互的主要形式.用形式化方法构建了基于线性时序逻辑的协商推理模型,该模型用线性时序逻辑描述在协商过程中Agent所处环境,自身能力、权力、知识、思维等随时间的变化,以及在系统运行时Agent采取异步行为.进一步完善了多Agent系统中自主的协商机制.     

基于时序逻辑的业务过程约束建模及验证*

提出一种可视化的约束规则建模语言(visual constraint modeling language, VCML),采用XYZ/E语言作为逻辑框架,统一定义约束规则和业务过程两种模型的形式化语义,为约束规则的自动验证提供形式化基础;然后基于模型检验(model checking)技术,简要讨论模型自动验证的实现方法;最后通过一个应用实例说明业务过程约束的建模。     

基于线性时序逻辑的最优巡回路径规划

基于线性时序逻辑(Linear temporal logic, LTL)的路径规划方法中, 多点巡回路径规划问题尚无有效解决方案. 为了在道路网络中实现最优巡回监测, 提出了基于LTL的最优巡回路径规划方法. 首先, 将环境建模成一个切换系统, 用LTL语言描述包含多个巡回点和障碍物的任务需求; 接着, 利用循环移位法构建能够融合任务需求和环境模型的扩展乘机自动机, 以建立路径信息完整的网络拓扑; 最后, 采用基于迪科斯彻法的最优综合算法搜索扩展乘机自动机网络上的最优路径, 从而获得能够满足复杂任务需求的最优巡回路径. 仿真结果表明, 该方法能够有效实现最优巡回路径规划.     

Petri网性质的线性时序逻辑描述与Spin检验

Petri网是描述并发系统的很直观的图形工具Spin是一种著名的分析验证并发系统性质的工具。本文首先论述Petri网性质的线性时序逻辑描述，研究用Promela编程描述Petri网和用Spin对Petri网性质进行检验的方法，最后通过两个具体的示例说明这种方法是成功的。     

命题线性时序逻辑的对偶模型问题的复杂性

定义了一个命题线性时序逻辑的对偶模型的概念.一个公式f的对偶模型是指f的满足以下条件的两个模型(即状态的w序列):在每个位置上这两个模型对原子命题的赋值都是对偶的.然后,对于确定一个公式f是否有对偶模型的判定问题(记为DM)和在一个Kripke-结构中确定是否存在从两个给定状态出发的对偶模型满足给定公式f的判定问题(记为KDM)的复杂性进行了研究.证明了以下结果:对于只含有F("Future")算子的命题线性时序逻辑,DM和KDM都是NP完全的;而对于以下命题线性时序逻辑,DM和KDM都是PSPACE完全的:含有F,X ("Next")算子的逻辑、含有U("Until")算子的逻辑、含有U,S,X算子的逻辑以及由Wolper给出的含有正规语言算子的逻辑(一般称为扩展时序逻辑,简称ETL).     

基于XYZ／E的CA认证系统描述与求精

时序逻辑语言XYZ／E在统一的逻辑框架下既能表示静态语义又能表示动态语义，可以实现从抽象描述到可执行程序的平滑过渡。本文建立了CA认证系统组件求精模型，对CA和RA组件用XYZ／E进行了描述和求精。     

Statecharts的组合语义与求精

由于简洁、直观的表达能力,Statecharts被用于许多反应系统的行为建模.Statecharts可表示不同抽象层次的系统行为,因而可用来表示逐步求精建模中各步的结果.但对于求精过程中下层是否保持了上层的语义、所建模型是否满足某些性质的问题,却难以在其自身的框架下进行讨论.在这方面,形式化语言XYZ/E可与其互补.XYZ/E是一种可执行线性时序逻辑语言,既可表示系统的性质,又可表示系统的行为.递归地在基本迁移系统上解释Statecharts语义,用XYZ/E公式表示它的时序语义.这一语义是模块级可组合的.求精过程的语义保持,可直接从语义定义得到保证.Statecharts所描述的系统行为模型和性质在同一个逻辑中表示,因此,系统行为是否满足所需性质的问题可由逻辑蕴涵式表示.     

基于时态逻辑的软件体系结构描述语言及其可视化环境

在时态逻辑语言XYZ／E的基础上,建立了一种以可视化图形表示的软件体系结构描述语言XYZ／ADL．它可同时描述软件体系结构的静态与动态行为,能在统一的形式框架下完成不同抽象层次体系结构设计之间的逐步过渡,从而将模块化程序设计方法和基于规范的逐步求精方法有机地结合起来。     

UML活动图的时序逻辑语义

UML活动图可以表示不同抽象级的控制流,很适合用于对系统的行为建模．但是缺乏精确的语义使得难以对它所表示的系统行为进行分析．XYZ／E是一可执行线性时序逻辑语言,既可描述系统的动态行为又可表示程序性质,用它对活动图形式化后,就可在统一的逻辑框架下分析活动图的性质．定义了一个有向图结构用以表示UML活动图,再给出其XYZ／E语义,并用一个例子说明活动图到XYZ／E的语义转换,为进一步的分析提供形式化基础．     

CSCW时序逻辑模型交互行为的正确性研究

正确性是软件系统最重要的质量因素。CSCW的时序逻辑模型全面地描述了CSCW系统的行为,较好地实现了CSCW的系统要求。文章在XYZ系统的框架内,从CSCW时序逻辑模型交互行为中每一个进程的正确性和交互行为并发性的正确性两个方面,对CSCW的时序逻辑模型交互行为描述的正确性进行了论证,这为CSCW时序逻辑模型的实现奠定了坚实的基础。     

使用时序逻辑检测软件需求阶段的特征干扰

针对需求阶段的特征干扰问题,提出了使用时序逻辑语言XYZ／E检测特征干扰的方法。最后给出了一个简单的升降机系统的实例。     

软件体系结构求精方法研究

1.引言软件设计在相当大的程度上可与建筑设计相类比,在古今中外建筑设计中,有诸多如欧洲的“歌特式”、“巴洛克式”、“维多利亚式”,中国的“园林式”、“宫廷式”等不同结构风格的建筑。同样在软件设计上,经过多年的理论探索和工程实践,也逐渐形成了一系列不同结构风格的软件体系结构。如UNIX操作系统中的管道一过滤器(pipe-filters)风格、分布式系统中典型的客户机/服务器(client/server)风格以及通信系统中的分层(layer)系统等等。