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 invariant ellipsoids for discrete-time systems by saturated optimal controls

Analytical approximation of the maximal invariant ellipsoid for discrete-time linear systems with saturated optimal control is established, which is less conservative than existing computationally un-intensive results. Simultaneously, necessary and sufficient conditions for such approximation being equal to the real maximal invariant ellipsoid is presented. All results are given analytically and can easily be implemented in practice. An illustrative example is given to show the effectiveness of the proposed approach.     

扩展时间事件图的能达性与能控序列

利用图论方法在双子结构中研究扩展时间事件图的某些问题,获得了能达性的一个充分必要条件和基于能达性的标准结构。在此基础上,把监控理论中的能控序列的分量分为本质不同的３类,进而得到能控序列的简化求解方法。     

Syntax-driven Behavior Partitioning for Model-checking of Esterel Programs

We consider the issue of exploiting the structural form of Esterel programs to partition the algorithmic RSS (reachable state space) fix-point construction used in model-checking techniques. The basic idea sounds utterly simple, as seen on the case of sequential composition: in P; Q, first compute entirely the states reached in P, and then only carry on to Q, each time using only the relevant transition relation part. Here a brute-force symbolic breadth-first search would have mixed the exploration of P and Q instead, in case P had different behaviors of various lengths, and that would result in irregular BBD representation of temporary state spaces, a major cause of complexity in symbolic model-checking.Difficulties appear in our decomposition approach when scheduling the different transition parts in presence of parallelism and local signal exchanges. Program blocks (or “Macro-states”) put in parallel can be synchronized in various ways, due to dynamic behaviors, and considering all possibilities may lead to an excessive division complexity. The goal is here to find a satisfactory trade-off between compositional and global approaches. Concretely we use some of the features of the TiGeR BDD library, and heuristic orderings between internal signals, to have the transition relation progress through the program behaviors to get the same effect as a global RSS computation, but with much more localized transition applications. We provide concrete benchmarks showing the usefulness of the approach.     

Predictable service overlay networks: Predictability through adaptive monitoring and efficient overlay construction and management

Providing bounded communication among participating nodes is significant for distributed systems. Internet-based applications suffer with lower performance due to absence of bounded latency. We describe PSON, an overlay network solution to this challenging problem. PSON has two components. The monitoring component, SyncProbe, utilizes efficient and adaptive monitoring techniques to measure latency, detect packet loss, and provide real-time estimates of maximum expected latency along paths of an Internet substrate. The QoSMap component constructs and manages overlay such that it yields application-level QoS and provides resilience against network failures. A distinctive feature of QoSMap is construction of QoS-compliant backup paths which facilitate in overlay management and operation during the period when primary overlay paths violate QoS. We evaluate PSON on PlanetLab to provide predictable communication for applications with different topology and QoS requirement. Our experiments confirm the effectiveness of PSON in providing an inexpensive and efficient application-layer solution to Internet’s unpredictable behavior.     

Chance-constrained model predictive control for spacecraft rendezvous with disturbance estimation

A robust Model Predictive Controller (MPC) is used to solve the problem of spacecraft rendezvous, using the Hill-Clohessy-Wiltshire model with additive disturbances and line-of-sight constraints. Since a standard (non-robust) MPC is not able to cope with disturbances, a robust MPC is designed using a chance-constrained approach for robust satisfaction of constraints in a probabilistic sense. Disturbances are modeled as Gaussian allowing for an explicit transformation of the probabilistic constraints into simple algebraic constraints. To estimate the distribution parameters a predictor of disturbances is proposed. Both robust and non-robust MPC control laws are compared using the Monte Carlo method, which shows the superiority of the robust MPC.     

赋时Petri网的一种符号分析算法

有序二叉决策图（0rdered Binary Decision Disgram-OBDD）是布尔函数表示的规范型，布尔函数的复杂运算可以基于OBDD得到极大地简化实现。在讨论基于OBDD的有界Petri网符号分析算法的基础上，对赋时位置Petri网的符号分析进行了研究，构造了一种扩展标识向量，给出了赋时Petri网分析的一种符号OBDD算法，实现了赋时Petri网的隐式描述与分析。实验表明，符号算法能处理较大规模赋时Petri网问题。     

Theories with self-application and computational complexity

Applicative theories form the basis of Feferman’s systems of explicit mathematics, which have been introduced in the 1970s. In an applicative universe, all individuals may be thought of as operations, which can freely be applied to each other: self-application is meaningful, but not necessarily total. It has turned out that theories with self-application provide a natural setting for studying notions of abstract computability, especially from a proof-theoretic perspective. This paper is concerned with the study of (unramified) bounded applicative theories which have a strong relationship to classes of computational complexity. We propose new applicative systems whose provably total functions coincide with the functions computable in polynomial time, polynomial space, polynomial time and linear space, as well as linear space. Our theories can be regarded as applicative analogues of traditional systems of bounded arithmetic. We are also interested in higher-type features of our systems; in particular, it is shown that Cook and Urquhart’s system is directly contained in a natural applicative theory of polynomial strength.     

Combined Petri net modelling and AI-based heuristic hybrid search for flexible manufacturing systems—part II. Heuristic hybrid search

This two-part paper presents modelling and scheduling approaches of flexible manufacturing systems using Petri nets (PNs) and artificial intelligence (AI)-based heuristic search methods. In Part I, PN-based modelling approaches and basic AI-based heuristic search algorithms were presented. In Part II, a new heuristic function that exploits PN information is proposed. Heuristic information obtained from the PN model is used to dramatically reduce the search space. This heuristic is derived from a new concept, the resource cost reachability matrix, which builds on the properties of B-nets proposed in Part I. Two hybrid search algorithms, (1) an approach to model dispatching rules using analysis information provided by the PN simulation and (2) an approach of the modified stage-search algorithm, are proposed to reduce the complexity of large systems. A random problem generator is developed to test the proposed methods. The experimental results show promising results.     

Petri网可达树的构造与实现

讨论了Petri网可达树的构造方法，给出了相应的算法和实现技术，对基于Petri网可达树的并发系统的动态性能分析具有一定的参考价值。