Symbolic Verification and Analysis of Discrete Timed Systems

This paper presents a novel approach for real-time model checking. It combines the efficiency of traditional symbolic model checking with possibilities to describe and specify real-time systems. Using multi-terminal binary decision diagrams to represent time and time intervals, it becomes possible to transfer efficient algorithms and optimization heuristics known from standard CTL model checking to real-time applications. By introducing a new variant of models called I/O-interval structures we can describe systems in a modular way. Interval structures allow model composition of real-time structures such that state explosion effects are greatly reduced. Besides model checking we also present analysis algorithms which allow to compute key properties like system latencies and minimal response times from the structures describing the system. The practical applicability is proven by experimental results, computed by the verification system RAVEN, which implements all described algorithms, including counterexample generation and waveform visualization.     

Discrete Events in Power Systems

The relevance of Discrete Event System theory (whether synthetic or analytic) to power system analysis and control is not clear. However, based on several characterizations of the domain of discrete systems set forth in the January 1989 Special Issue of the IEEE Proceedings, on Dynamics of discrete event systems (Ho, 1989), we attempt to delineate several power system control problems that may be amenable to analysis by DEDS methodologies. While the author is not qualified to judge whether the latter can speak to any of the examples, it may be relevant that in all cases the problems are non-trivial and in need of further contributions toward improved solutions, especially in view of the ongoing radical restructuring of the industry. The continuous process that is instantiated in the functioning of a power system is observed via three more or less diverse variables. Two of these, the scaler system frequency and the vector system voltage profile, are in principle mensurable physical phenomena; the third, system security, is a quality represented by a set membership conditioned on an inferred relationship between the two physical system variables and future realizations of one or more classes of autonomous stochastic phenomena. (These latter may be internal or external to the physical system, such as, e.g., respectively, equipment failure mechanisms and weather events.)     

Events And Interrupts in Tightly Coupled Multiprocessors

In a decentralized multiprocessor, events must be stored, queued, and acknowledged. This can be accomplished by implementing a special event receiver called a synapse and by utilizing several forms of acknowledge.     

A New Class of Supervisors for Timed Discrete Event Systems Under Partial Observation

Brandin and Wonham have developed a supervisory control framework for timed discrete event systems (TDESs) in order to deal with not only logical specifications but also temporal specifications. Lin and Wonham have extended this framework to the partial observation case, and presented necessary and sufficient conditions for the existence of a nonblocking supervisor under partial observation. In this paper, we define a new class of supervisors for TDESs under partial observation. We then present necessary and sufficient conditions for the existence of a nonblocking supervisor defined in this paper. These existence conditions of our supervisor are weaker than those of Lin and Wonham's supervisor. Note, however, that the price that must be paid to weaken the existence conditions is the higher computational cost. Moreover, given a closed regular language, we study computation of a sublanguage that satisfies the existence conditions of our supervisor. We present an algorithm for computing such a sublanguage larger than the supremal closed, controllable, and normal sublanguage.     

Some Ergodic Results on Stochastic Iterative Discrete Events Systems

This paper deals with the asymptotic behavior of the stochastic dynamics of discrete event systems. In this paper we focus on a wide class of models arising in several fields and particularly in computer science. This class of models may be characterized by stochastic recurrence equations in ^K of the form T(n+1) = _n+1(T(n)) where _n is a random operator monotone and 1—linear. We establish that the behaviour of the extremas of the process T(n) are linear. The results are an application of the sub-additive ergodic theorem of Kingman. We also give some stability properties of such sequences and a simple method of estimating the limit points.     

离散事件动态系统的D-自动机模型

首先引入D-子集和D-语言的概念,在此基础上给出了一类离散事件动态系统的一般形式化表述--D-自动机模型,并讨论了受控系统的动态行为.最后研究了系统的状态可达性问题.     

具有模型和实际差异的非线性离散动态系统最优控制

针对模型与实际存在一定差异的情况,提出了一种求解非 线性离散系统最段控制的动态系统优化和参数估计集成（Ｄｙｎａｍｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｓｙｓｔｅｍ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｐａｒａｍｅｔｅｒ Ｅｓｔｉｍａｔｉｏｎ,简称ＤＩＳＯＰＥ）的研究法。推导出一组求解一类有终端等式约束的非齐次的线性两点边值问题的递推公式,对于有终端等式约束的非线线性最优控制问题得到了在计算上易于实现的一种ＤＩＳＯＰＥ     

Timed Testing of Concurrent Systems

This paper is concerned with timing considerations for concurrent systems where the time needed by the individual actions is not known beforehand: it has long been suspected that the power of partial order semantics is needed here. We develop a suitable testing scenario to study this idea. With one view of timed behaviour, we can confirm that interval semiword semantics, a special partial order semantics, is indeed what can be observed with timed tests. With another view, our testing scenario leads to timed-refusal-trace semantics; this is a noninterleaving semantics, but it seems that it cannot be represented with partial orders in a meaningful way.     

Reduction of Timed Hybrid Systems

We consider a class of hybrid dynamical systems and obtain conditions under which the behavior of these systems can be reduced to a finite state automaton. Specifically, we consider timed automata with more general enabling regions coupling the continuous and discrete dynamics than those previously considered. We provide a necessary condition for the existence of a finite state reduction, together with examples showing that this condition is not sufficient. We then give two sufficient conditions that provide a large class of systems with general enabling regions which admit finite reductions.     

离散时间Petri网的模糊模型

离散时间Petri网是一种系统模拟和分析的有效工具，它可以结合图形和分析描述评估离散事件系统的动态执行．基于T—S模糊模型，提出用于描述离散时间Petri网的模糊模型，讨论该模型适应于TtPNs的情况，用以推广文章结论，并且给出用于TtPNs的线性模糊控制规则．同时，文章还给出TtPNs聚合的结论．     

离散时滞大系统的无条件稳定性

本文研究一类线性定常离散时滞大系统的无条件稳定性问题。首先利用m阵的性质,给出了一般离散时滞系统无条件渐近稳定的充分条件;接着建立了适应于离散时滞系统的比较原理,最后用向量李雅普诺夫函数法和集结(aggregatioa)方法,推得了线性定常离散时滞大系统无条件稳定的充分条件。这一条件归结为判定一个阶数等于子系统个数的实矩阵是否是一个m阵。一个简单的数值例子说明了本文得出的结果的应用。     

Optimal Control of Multi-Stage Discrete Event Systems With Real-Time Constraints

We consider discrete event systems involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal state trajectory that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider such a multi-stage problem with not only stage-dependent but also task-dependent cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing ldquovirtualrdquo deadlines at each stage except the last one, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that a sequence of solutions to single-stage problems with virtual deadlines updated at each step converges to the global optimal solution of the multi-stage problem. This leads to a virtual deadline algorithm (VDA) which is scalable in the number of processed tasks. We illustrate the scalability and efficiency of the VDA through numerical examples.     

Robust Stability For Uncertain Discrete Singular Systems With State Delay

A computationally simple stability condition for discrete singular systems with state delay is presented in this paper. Based on this, a robust stability result for such systems with structured parametric uncertainties is given. This condition ensures that, for all admissible uncertainties, the system under consideration is regular, causal and stable. Then D‐stability results for discrete singular delay systems are obtained. All the proposed conditions are easy to test.     

A Process Algebra for Timed Systems

A standard process algebra is extended by a new action σ which is meant to denote idling until the next clock cycle. A semantic theory based on testing is developed for the new language. This is characterised in terms of barbs, a variety of ready traces and also characterised as the initial theory generated by a set of equations.     

Timed Modal Logics for Real-Time Systems

In this paper, a timed modal logic L _c is presented for the specification and verification of real-time systems. Several important results for L _c are discussed. First we address the model checking problem and we show that it is an EXPTIME-complete problem. Secondly we consider expressiveness and we explain how to express strong timed bisimilarity and how to build characteristic formulas for timed automata. We also propose a compositional algorithm for L _c model checking. Finally we consider several control problems for which L _c can be used to check controllability.     

一种基于离散时间自动机的LTL性质检测工具

模型检测是一种自动完成性质验证的算法过程,在模型检测过程中会遇到状态空间爆炸的问题,即随系统规模的增长状态空间的大小呈指数增长,如何缓解此问题一直是研究者研究的重点.目前利用模型检测方法对线性时序逻辑(LTL)性质进行检测的工具还比较少,且效率都较低.介绍了一种基于离散时间自动机的LTL性质检测工具,采用了在状态空间中存储延迟序列(DS)的技术,对状态进行压缩存储,减小了时间空间的消耗,加快了检测速度.实验表明,该工具的检测效果是不错的,要好于同类工具,如DTSpin.