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

模型检查是一种用于并发系统的性质验证的算法技术.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的基础上,建立了一种以可视化图形表示的软件体系结构描述语言XYZ／ADL．它可同时描述软件体系结构的静态与动态行为,能在统一的形式框架下完成不同抽象层次体系结构设计之间的逐步过渡,从而将模块化程序设计方法和基于规范的逐步求精方法有机地结合起来。     

UML活动图的时序逻辑语义

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

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

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

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

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

Logic Based Abstractions of Real-Time Systems

When verifying concurrent systems described by transition systems, state explosion is one of the most serious problems. If quantitative temporal information (expressed by clock ticks) is considered, state explosion is even more serious. We present a notion of abstraction of transition systems, where the abstraction is driven by the formulae of a quantitative temporal logic, called qu-mu-calculus, defined in the paper. The abstraction is based on a notion of bisimulation equivalence, called , n-equivalence, where is a set of actions and n is a natural number. It is proved that two transition systems are , n-equivalent iff they give the same truth value to all qu-mu-calculus formulae such that the actions occurring in the modal operators are contained in , and with time constraints whose values are less than or equal to n. We present a non-standard (abstract) semantics for a timed process algebra able to produce reduced transition systems for checking formulae. The abstract semantics, parametric with respect to a set of actions and a natural number n, produces a reduced transition system , n-equivalent to the standard one. A transformational method is also defined, by means of which it is possible to syntactically transform a program into a smaller one, still preserving , n-equivalence.     

实时时序逻辑语言XYZ/RE到时间自动机的映射

时间自动机是一种重要的实时系统建模工具。本文建立了实时时序逻辑语言XYZ/RE到时间自动机的一种映射机制,将XYZ/RE所描述的系统进程直接转换为时间自动机,这样不但可以准确捕获实时系统功能和控制行为,还可以利用基于时间自动机的验证工具UPPAAL对XYZ/RE描述的系统正确性进行检测。最后本文通过一个实例的描述与检测,验证了映射机制的有效性。     

基于形式化描述的电梯控制系统的建模与仿真

研究电梯控制系统中组件之间复杂的信号传输关系。针对传统的建模方法不能同时精确描述系统模型的静态与动态语义的问题,从系统体系结构的组件与连接件入手,探讨形式化描述语言XYZ/ADL描述系统模型的特性,运用XYZ/ADL形式化地描述电梯控制系统的总体功能规范、主要组件的结构模型、组件之间信号传输的动态模型和电梯运行模型,并基于所构建的形式化描述模型实现系统的仿真运行。结果表明,基于XYZ/ADL描述的形式化模型能准确分析电梯组件之间复杂的信号传输关系,精确模拟电梯运行的各种状态。     

Specifying Real-Time Finite-State Systems in Linear Logic (Extended Abstract)

Abstract

Real-time finite-state systems may be specified in linear logic by means of linear implications between conjunctions of fixed finite length. In this setting, where time is treated as a dense linear ordering, safety properties may be expressed as certain provability problems. These provability problems are shown to be in pspace. They are solvable, with some guidance, by finite proof search in concurrent logic programming environments based on linear logic and acting as sort of model-checkers. One advantage of our approach is that either it provides unsafe runs or it actually establishes safety.