BACH:线性混成系统有界可达性模型检验工具

混成自动机的模型检验问题非常困难,即使是其中相对简单的一个子类--线性混成自动机,它的可达性问题仍然是不可判定的.现有的相关工具大都使用多面体计算来判定线性混成自动机状态空间的可达集,复杂度高、效率低,无法解决实际应用规模的问题.描述了一个面向线性混成系统有界可达性模型检验工具--BACH(bounded reacha...     

Path-oriented bounded reachability analysis of composed linear hybrid systems

The existing techniques for reachability analysis of linear hybrid systems do not scale well to the problem size of practical interest. The performance of existing techniques is even worse for reachability analysis of a composition of several linear hybrid automata. In this paper, we present an efficient path-oriented approach to bounded reachability analysis of composed systems modeled by linear hybrid automata with synchronization events. It is suitable for analyzing systems with many components by selecting critical paths, while this task was quite insurmountable before because of the state explosion problem. This group of paths will be transformed to a group of linear constraints, which can be solved by a linear programming solver efficiently. This approach of symbolic execution of paths allows design engineers to check important paths, and accordingly increase the faith in the correctness of the system. This approach is implemented into a prototype tool Bounded reAchability CHecker (BACH). The experimental data show that both the path length and the number of participant automata in a system checked using BACH can scale up greatly to satisfy practical requirements.     

On polyhedral estimates for reachable sets of discrete-time systems with bilinear uncertainty

We describe techniques for constructing external and internal polyhedral (parallelepiped-valued) estimates for reachability sets of discrete-time systems with bilinear uncertainty, i.e., systems with originally linear but incompletely specified dynamics, when system coefficients exhibit uncertainty of the interval type. Our primary attention is focused on internal estimates. The evolution of reachability set estimates is given by recursive relations. We give numerical modeling results.     

Synthesis of controllers for target problems of hybrid systems using approximate computation

This paper presents methodologies based on approximate computations for the target control problem of hybrid systems modelled by hybrid automata. The problem of backward reachability and its relation to the control synthesis is studied using approximate analysis techniques. The reachability operators, considering non-linear and linear dynamics with affine disturbances, are under-approximated using state space discretization that involves hyper-cubes. The timing information provided by the backward reachability computation is used in order to design a sub-optimal controller. The computational techniques are applied to the batch evaporator benchmark process which has practical interest.     

Towards an Efficient Path-Oriented Tool for Bounded Reachability Analysis of Linear Hybrid Systems using Linear Programming

The existing techniques for reachability analysis of linear hybrid automata do not scale well to problem sizes of practical interest. Instead of developing a tool to perform reachability check on all the paths of a linear hybrid automaton, a complementary approach is to develop an efficient path-oriented tool to check one path at a time where the length of the path being checked can be made very large and the size of the automaton can be made large enough to handle problems of practical interest. This approach of symbolic execution of paths can be used by design engineers to check important paths and thereby, increase the faith in the correctness of the system. Unlike simple testing, each path in our framework represents a dense set of possible trajectories of the system being analyzed. In this paper, we develop the linear programming based techniques towards an efficient path-oriented tool for the bounded reachability analysis of linear hybrid systems.     

On the analysis of nonlinear nilpotent switched systems using the Hall–Sussmann system

We consider an open problem on the stability of nonlinear nilpotent switched systems posed by Daniel Liberzon. Partial solutions to this problem were obtained as corollaries of global nice reachability results for nilpotent control systems. The global structure is crucial in establishing stability. We show that a nice reachability analysis may be reduced to the reachability analysis of a specific canonical system, the nilpotent Hall–Sussmann system. Furthermore, local nice reachability properties for this specific system imply global nice reachability for general nilpotent systems. We derive several new results revealing the elegant Lie-algebraic structure of the nilpotent Hall–Sussmann system.     

Hierarchical reachability graph of bounded Petri nets forconcurrent-software analysis

Petri nets have been proposed as a promising tool for modeling and analyzing concurrent-software systems such as Ada programs and communication protocol software. Among analysis techniques available for Petri nets, the most general approach is to generate all possible states (markings) of the system in a form of a so-called reachability graph. However, this conventional reachability graph approach is inefficient or intractable, even for a bounded Petri net, due to state explosion in many practical applications. To cope with this problem, this paper proposes a method for constructing a hierarchically organized state space called the hierarchical reachability graph (HRG). Using the HRG, we obtain necessary and sufficient conditions for reachability and deadlock, as well as algorithms to test whether a given state or marking is reachable from the initial state and whether there is a deadlock state (a state with no successor states)     

Efficient synthesis of production schedules by optimization of timed automata

For industrial systems with multiple products or alternative production paths, the time-optimal assignment of production steps to available units is often economically indispensable. Among the several methods proposed for solving such job-shop scheduling problems, techniques based on reachability analysis for timed automata (TA) have gained attention recently. It was proposed recently to integrate techniques known from mixed-integer programming (MIP) into reachability analysis for TA to establish an efficient pruning of the search graph. This paper further improves the efficiency of the algorithm by excluding suboptimal or redundant solutions from the search space. For several benchmark problems, it is shown that the proposed approach can produce better schedules in a given computation time as are obtained by applying pure MIP to large problem instances.     

Cascades of tree-automata and computations in universal algebras

It is possible to define a general notion of cascade composition for tree-automata in a way very similar to the case of ordinary automata. For this cascade composition we show necessary and sufficient conditions of decomposability like those of the ordinary case. Also some kinds of associativity properties continue to hold.A further generalization leads us to apply these results to a large class of universal algebras, and by some examples it is shown that we can decompose some familiar algebras into cascades of tree-automata. Moreover, the cascades obtained identify some algorithms that are the common ones for computing in the algebras considered.Supported by CNR Rome, and by N.R.C. of Canada, grant A-4096.Supported by CNR Rome, and by N.R.C. of Canada, grant A-4096.     

Incremental integration testing of concurrent programs

We present a method for selecting test sequences for concurrent programs from labeled transitions systems (LTS). A common approach to selecting test sequences from a set of LTSs is to derive a global LTS, called the reachability graph, and then force deterministic program executions according to paths selected from the graph. However, using a reachability graph for test path selection introduces a state explosion problem. To overcome this problem, a reduced graph can be generated using incremental reachability analysis, which consists of repeatedly generating a reachability graph for a subset of LTSs, reducing this graph, and using the reduced graph in place of the original LTSs. Unfortunately, existing incremental reachability analysis techniques generate reduced graphs with insufficient information for deterministic testing. We present an incremental approach to testing concurrent programs. Incremental testing consists of incremental reachability analysis for test path selection and deterministic testing for test execution. We define a new type of reachability graph for incremental analysis, called an annotated labeled transition system (ALTS). An ALTS is an LTS annotated with information necessary for deterministic testing. We propose practical coverage criteria for selecting tests paths from an ALTS and present an ALTS reduction algorithm. The results of several case studies are reported     

Time-optimal control for discrete-time hybrid automata

In this paper, the problem of time-optimal control for hybrid systems with discrete-time dynamics is considered. The hybrid controller steers all trajectories starting from a maximal set to a given target set in minimum time. We derive an algorithm that computes this maximal winning set. Also, algorithms for the computation of level sets associated with the value function rather than the value function itself are presented. We show that by solving the reachability problem for the discrete time hybrid automata we obtain the time optimal solution as well. The control synthesis is subject to hard constraints on both control inputs and states. For linear discrete-time dynamics, linear programming and quantifier elimination techniques are employed for the backward reachability analysis. Emphasis is given on the computation of operators for non-convex sets using an extended convex hull approach. A two-tank example is considered in order to demonstrate the techniques of the paper.     

Controller synthesis for safety and reachability via approximate bisimulation

In this paper, we consider the problem of controller design using approximately bisimilar abstractions with an emphasis on safety and reachability specifications. We propose abstraction-based approaches to controller synthesis for both types of specifications. We start by synthesizing a controller for an approximately bisimilar abstraction. Then, using a concretization procedure, we obtain a controller for our initial system that is proved “correct by design”. We provide guarantees of performance by giving estimates of the distance of the synthesized controller to the maximal (i.e., the most permissive) safety controller or to the time-optimal reachability controller. Finally, we use these techniques, combined with discrete approximately bisimilar abstractions of switched systems developed recently, for switching controller synthesis.     

基于可达关系的安全协议保密性分析

借助形式化的方法或工具分析安全协议是非常必要而且行之有效的.进程演算具有强大的描述能力和严格的语义,能够精确刻画安全协议中各个参与者之间的交互行为.作者以进程演算为基础,嵌入消息推理系统以弥补进程演算固有的缺乏数据结构支持的特点,尝试地提出了一个基于可达关系的安全协议保密性分析模型.基于此模型,形式化地描述了安全协议的保密性,证明了一定限制条件下的可判定性.并且以TMN协议为例,给出了该模型的实例研究.     

Reachability analysis of switched linear discrete singular systems

This paper studies the reachability problem of the switched linear discrete singular （SLDS） systems. Under the condition that all subsystems are regular, the reachability of the SLDS systems is characterized based on a peculiar repeatedly introduced switching sequence. The necessary and sufficient conditions are obtained for the reachability of the SLDS systems.     

Discrete-time linear periodic systems: gramian and modal criteria for reachability and controllability†

This paper deals with the reachability and controllability of periodic discrete-time systems. First, we supply two necessary and sufficient complete reachability conditions, which apply to reversible and non-reversible systems, respectively. Then, a necessary and sufficient complete controllability condition is provided. This condition, as well as the complete reachability criteria, is given in terms of the reachability gramian matrix. Equivalent modal criteria for reachability and controllability are established in the second part of the paper.     

Reachability analysis of constrained switched linear systems

In this note, we investigate the reachability of switched linear systems with switching/input constraints. We prove that, under a mild assumption of the feasible switching signals, the reachability set is the reachable subspace of the unconstrained system. We also address the local reachability for switched linear systems with input constraints and present a complete criterion for a general class of switched linear systems.     

FAST: acceleration from theory to practice

Fast acceleration of symbolic transition systems (Fast) is a tool for the analysis of systems manipulating unbounded integer variables. We check safety properties by computing the reachability set of the system under study. Even if this reachability set is not necessarily recursive, we use innovative techniques, namely symbolic representation, acceleration and circuit selection, to increase convergence. Fast has proved to perform very well on case studies. This paper describes the tool, from the underlying theory to the architecture choices. Finally, Fast capabilities are compared with those of other tools. A range of case studies from the literature is investigated. This paper is mainly based on results presented at CAV 2003, TACAS 2004 and ATVA 2005.     

On reachability graphs of Petri nets

Petri net is a powerful tool for system analysis and design. Several techniques have been developed for the analysis of Petri nets, such as reachability trees, matrix equations and reachability graphs. This article presents a novel approach to constructing a reachability graph, and discusses the application of the reachability graph to Petri nets analysis.     

On the reachability in any fixed time for positive continuous-time linear systems

This paper deals with the reachability of continuous-time linear positive systems. The reachability of such systems, which we will call here the strong reachability, amounts to the possibility of steering the state in any fixed time to any point of the positive orthant by using nonnegative control functions. The main result of this paper essentially says that the only strongly reachable positive systems are those made of decoupled scalar subsystems. Moreover, the strongly reachable set is also characterized.