Diagnosis of repeated failures for discrete event systems with linear-time temporal-logic specifications

In our earlier work, we introduced a state-based approach for the diagnosis of repeatedly occurring failures in discrete event systems (DESs). Since temporal logic provides a simpler way of specifying system properties; in this paper, a temporal-logic-based approach for diagnosing the occurrence of a repeated number of failures is developed. Linear-time temporal-logic (LTL) formulae are used to represent the specifications of DESs. Notions of prediagnosability for failures and diagnosability for repeated failures are introduced in the setting of temporal logic. A polynomial algorithm for the test of prediagnosability for failures is provided. The diagnosis problem for repeated failures in the temporal-logic setting is reduced to one in a state-based setting, and so the prior results of a state-based repeated failure diagnosis can be applied. Finally, a simple example is given for illustration. Note to Practitioners-Certain failures in a system are repeatable, such as routing errors in a manufacturing system. A theory for the diagnosis of such failures was presented in an earlier work of Jiang et al. The present paper uses temporal logic to specify such failures. It turns out that repeatable failures can be specified as violations of invariant properties (i.e., properties that must always hold). Given an invariant property that the system must always satisfy, an algorithm is presented to refine the system model and label those states of the refined system where the property is violated. The problem of repeated diagnosis then requires determining, within a bounded delay, each time a "failure-state" is visited. For this analysis, the existing theory developed by Jiang et al. is used.     

Specification of Synchronizing Processes

The formalism of temporal logic has been suggested to be an appropriate tool for expressing the semantics of concurrent programs. This paper is concerned with the application of temporal logic to the specification of factors affecting the synchronization of concurrent processes. Towards this end, we first introduce a model for synchronization and axiomatize its behavior. SYSL, a very high-level language for specifying synchronization properties, is then described. It is designed using the primitives of temporal logic and features constructs to express properties that affect synchronization in a fairly natural and modular fashion. Since the statements in the language have intuitive interpretations, specifications are humanly readable. In addition, since they possess appropriate formal semantics, unambiguous specifications result.     

Specification and analysis of intercomponent communication

The correctness, safety and robustness of the specification of a critical system are assessed through a combination of rigorous specification capture and inspection, formal analysis of the specification, and execution and simulation of the specification. Any integrated approach to specifying critical systems should support all three activities. Embedded systems pose special challenges to the specification and analysis of intercomponent communication. The authors present a formal approach which lets the interface specifications serve as kernels that enforce safety and simple liveness constraints     

On Closure Under Stuttering

For over a decade, researchers in formal methods have tried to create formalisms that permit natural specification of systems and allow mathematical reasoning about their correctness. The availability of fully automated reasoning tools enables non-experts to use formal methods effectively—their responsibility reduces to specifying the model and expressing the desired properties. Thus, it is essential that these properties be represented in a language that is easy to use, sufficiently expressive and succinct. Linear-time temporal logic (LTL) is a formalism that has been used extensively by researchers for program specification and verification. One of the desired properties of LTL formulas is closure under stuttering. That is, we do not want the interpretation of formulas to change over traces where some states are repeated. This property is important from both practical and theoretical prospectives; all properties which are closed under stuttering can be expressed in LTL_–X—a fragment of LTL without the next operator. However, it is often difficult to express properties in this fragment of LTL. Further, determining whether a given LTL property is closed under stuttering is PSPACE-complete. In this paper, we introduce a notion of edges of LTL formulas and present a formal theory of closure under stuttering. Edges allow natural modelling of systems with events. Our theory enables syntactic reasoning about whether the resulting properties are closed under stuttering. Finally, we apply the theory to the pattern-based approach of specifying temporal formulas.     

Linear Time Logic Control of Discrete-Time Linear Systems

The control of complex systems poses new challenges that fall beyond the traditional methods of control theory. One of these challenges is given by the need to control, coordinate and synchronize the operation of several interacting submodules within a system. The desired objectives are no longer captured by usual control specifications such as stabilization or output regulation. Instead, we consider specifications given by linear temporal logic (LTL) formulas. We show that existence of controllers for discrete-time controllable linear systems and LTL specifications can be decided and that such controllers can be effectively computed. The closed-loop system is of hybrid nature, combining the original continuous dynamics with the automatically synthesized switching logic required to enforce the specification     

在 XYZ/ E中实现混成实时系统——蒸气锅炉控制问题的解决

XYZ/E是一个时序逻辑系统,同时也是一种时序逻辑程序设计语言。XYZ/E能够在统一的框架下表示高层和低层的描述,所以便于软件系统的描述与实现。该文对基于XYZ/E的蒸气锅炉问题进行了描述与实现,并介绍了为该问题实现的图形用户界面.     

一个支持规约获取的形式规约语言

该文介绍了形式规约语言LFC设计的一些主要方面，并通过例子说明了LFC的一些特色。形式规约语言LFC是为支持软件形式规约的获取工作而开发的。该语言以一种新的递归函数，即定义在上下文无关语言上的递归函数为基础，以上下文无关语言为数据类型，在语言级支持规约获取。LFC语言已被用作形式规约获取系统SAQ的一部分。使用表明，LFC是一个能力强、易使用的语言，适合软件形式规约获取之用，并且适合其它一些用途。     

Active diagnosis of discrete-event systems

The need for accurate and timely diagnosis of system failures and the advantages of automated diagnostic systems are well appreciated. However, diagnosability considerations are often not explicitly taken into account in the system design. In particular, design of the controller and that of the diagnostic subsystem are decoupled, and this may significantly affect the diagnosability properties of a system. The authors present an integrated approach to control and diagnosis. More specifically, they present an approach for the design of diagnosable systems by appropriate design of the system controller. This problem, which they refer to as the active diagnosis problem, is studied in the framework of discrete-event systems (DESs); it is based on prior and new results on the theory of diagnosis for DESs and on existing results in supervisory control under partial observations. They formulate the active diagnosis problem as a supervisory control problem where the legal language is an “appropriate” regular sublanguage of the regular language generated by the system. They present an iterative procedure for determining the supremal controllable, observable, and diagnosable sublanguage of the legal language and for obtaining the supervisor that synthesizes this language. This procedure provides both a controller that ensures diagnosability of the closed-loop system and a diagnoser for online failure diagnosis. The procedure can be implemented using finite-state machines and is guaranteed to converge in a finite number of iterations. The authors illustrate their approach using a simple pump-valve system     

An empirical study of control logic specifications for programmable logic controllers

This paper presents an empirical study of control logic specifications used to document industrial control logic code in manufacturing applications. More than one hundred input/output related property specifications from ten different reusable function blocks were investigated. The main purpose of the study was to provide understanding of how the specifications are expressed by industrial practitioners, in order to develop new tools and methods for specifying control logic software, as well as for evaluating existing ones. In this paper, the studied specifications are used to evaluate linear temporal logic in general and the specification language ST-LTL, tailored for functions blocks, in particular. The study shows that most specifications are expressed as implications, that should always be fulfilled, between input and output conditions. Many of these implications are complex since the input and output conditions may be mixed and involve sequences, timer issues and non-boolean variables. Using ST-LTL it was possible to represent all implications of this study. The few non-implication specifications could be specified in ST-LTL as well after being altered to suit the specification language. The paper demonstrates some advantages of ST-LTL compared to standard linear temporal logic and discusses possible improvements such as support for automatic rewrite of complex specifications.     

Specification of communicating processes: temporal logic versus refusals-based refinement

In this paper we consider the relationship between refinement-oriented specification and specifications using a temporal logic. We investigate the extent to which one can check whether a program in a process algebra, such as Communicating Sequential Processes (CSP), satisfies a temporal logic specification using a refinement-based model checker, such as FDR. We consider what atomic formulae are appropriate in a temporal logic for specifying communicating processes, in particular where one wants to talk about the availability of events. We then show that, perhaps surprisingly, the standard stable failures model is not adequate for capturing specifications in such a logic: instead the refusal traces model must be used. We formalise the logic by giving it a semantics in this model. We show that the temporal operators eventually and until, and negation, cannot, in general, be tested for via simple refinement checks. For the remaining fragment of the logic, we present a translation into simple refinement checks. Finally, we show that refusal traces equivalence is characterised by a slightly augmented version of that fragment. M. J. Butler     

基于梯形逻辑的联锁系统形式化验证方法

铁路联锁系统设计通常采用梯形逻辑进行建模。为了实现对铁路联锁系统进行形式化验证的目的,根据梯形逻辑的状态变迁语义,将梯形逻辑表示的联锁系统模型转换成模型检测工具NuSMV的语言,并将铁路联锁系统的安全需求表示为计算树逻辑(CTL),最后实现基于NuSMV的铁路联锁系统设计模型的形式化验证。     

Building a knowledge base: an example

The main goal of this paper is to illustrate applications of some recent developments in the theory of logic programming to knowledge representation and reasoning in common sense domains. We are especially interested in better understanding the process of development of such representations together with their specifications. We build on the previous work of Gelfond and Przymusinska in which the authors suggest that, at least in some cases, a formal specification of the domain can be obtained from specifications of its parts by applying certain operators on specifications called specification constructors and that a better understanding of these operators can substantially facilitate the programming process by providing the programmer with a useful heuristic guidance. We discuss some of these specification constructors and their realization theorems which allow us to transform specifications built by applying these constructors to declarative logic programs. Proofs of two such theorems, previously announced in a paper by Gelfond and Gabaldon, appear here for the first time. The method of specifying knowledge representation problems via specification constructors and of using these specifications for the development of their logic programming representations is illustrated by design of a simple, but fairly powerful program representing simple hierarchical domains. This revised version was published online in June 2006 with corrections to the Cover Date.     

用带时钟变量的线性时态逻辑扩充Object-Z*

Object-Z是形式规格说明语言Z的面向对象扩充,适合描述大型面向对象软件规格说明,但它不能很好地描述连续性实时变量和时间限制。线性时态逻辑能够描述实时系统,但不能很好地处理连续时间关系,也不能很好地模块化描述形式规格说明。首先用时钟变量扩充线性时态逻辑,接着提出了一个方法——用带时钟变量的时态逻辑(LTLC)来扩充Object-Z。用LTLC扩充的Object-Z是一个模块化规格说明语言,是Object-Z语法和语义的最小扩充,其最大优点在于它能方便地描述和验证复杂的实时软件规格说明。     

Abstract Implementation of Algebraic Specifications in a Temporal Logic Language

A formal technique for incorporating two specification paradigms is presented,in which an algebraic specification is implemented by a set of abstract procedures specified in pre and post-condition style.The link between the two level specifications is provided via a translation from terms of algebraic specifications into temporal logic formulae representing abstract programs.In terms of translation,a criterion for an abstract implementation satisfying its specification is given,which allows one to check the consistency between the two levels of specifications.The abstract implementations can be refined into executable code by refining each abstract procedure in it.It is proved that the satisfication relation between a specification and its implementations is preserved by such refinement steps.     

Verifying specifications in the language L against temporal properties nonexpressible in this language

Verification methods for reactive algorithms specifications in the language L are considered. The verification is performed with respect to properties expressed in the class GR(1) of the temporal logic LTL and is reduced to checking the satisfiability of formulas in the language L.     

面向航天嵌入式软件的形式化建模方法

航天嵌入式软件是航天型号任务成败的关键之一.航天嵌入式软件是一种周期性、多模式的软件.软件的每个模式表示系统处于一定的状态,并进行相应的复杂计算.因此,提出了一种名为SPARDL的形式化建模方法.为了满足型号应用的需求,对这一方法进行了若干改进.为了表达航天器的时序性质,提出了一种基于区间逻辑的性质规范语言.为了支持工业应用,还设计了代码生成方法.这一建模方法已在航天工业领域得到了应用.     

具有多项式时间复杂性的离散事件系统安全诊断

离散事件系统的故障诊断能将已发生的不可观故障事件及时诊断出来,但往往容易忽略故障诊断期间系统的安全性.为解决这一问题,提出了一种具有多项式时间复杂性的安全故障诊断方法.先对离散事件系统的安全可诊断性进行了形式化,再通过构造一个非法语言识别器对系统被禁止操作序列进行识别,并在此基础上构建了一个对系统实施安全诊断的安全验证器,得到了一个关于离散事件系统安全可诊断性的充分必要条件,实现了对系统的安全故障诊断.同时,通过对安全验证器的构建与安全可诊断性的判定的复杂性分析,得到了该安全故障诊断方法可在多项式时间内实现等结论.     

Temporal-logic property preservation under Z refinement

Formal specification languages such as Z, B and VDM are used in the incremental development of abstract specifications (suitable for establishing required properties) to more concrete specifications (resembling the final implementation). This incremental development process, known as refinement, preserves all observable properties of the original abstract specification. Recent research has looked at applying temporal-logic model checking to such specification languages. While this assists in the establishment of properties of the abstract specification, temporal-logic properties typically refer to state variables which are regarded as non-observable. Hence, such properties are not guaranteed to be preserved by refinement. This paper investigates the classes of temporal-logic properties which are preserved by refinement, and for some of those properties that are not preserved in general, the restrictions on the refinement process under which they are preserved. Results are presented for the temporal logics LTL, CTL and the μ-calculus and the formal specification language Z. They apply equally, however, to related formal specification languages such as B and VDM.     

A model advisor for NuSMV specifications

Among possible model validation techniques able to identify defects early in the system development, model review aims also at determining if a model is of sufficient quality, where quality is measured as the absence of certain faults. In this paper, we tackle the problem of automatic reviewing NuSMV formal specifications by developing a model advisor which helps to assure given model qualities for NuSMV programs. Vulnerabilities and defects a developer can introduce during the modeling activity using NuSMV are expressed as the violation of formal meta-properties. These meta-properties are then mapped to temporal logic formulas, and the NuSMV model checker itself is used as the engine of our model advisor to notify meta-properties violations, so revealing the absence of some quality attributes of the specification. As a proof of concept, we also report the result of applying this review process to several NuSMV specifications.