Abstractions for hybrid systems

We present a procedure for constructing sound finite-state discrete abstractions of hybrid systems. This procedure uses ideas from predicate abstraction to abstract the discrete dynamics and qualitative reasoning to abstract the continuous dynamics of the hybrid system. It relies on the ability to decide satisfiability of quantifier-free formulas in some theory rich enough to encode the hybrid system. We characterize the sets of predicates that can be used to create high quality abstractions and we present new approaches to discover such useful sets of predicates. Under certain assumptions, the abstraction procedure can be applied compositionally to abstract a hybrid system described as a composition of two hybrid automata. We show that the constructed abstractions are always sound, but are relatively complete only under certain assumptions.     

概率计算树逻辑的限界模型检测

为了缓解概率计算树逻辑模型检测中的状态空间爆炸问题,提出了概率计算树逻辑的限界模型检测技术.该技术首先定义概率计算树逻辑的限界语义,并证明其正确性;之后,通过实例说明在传统限界模型检测中,以路径长度作为判断检测过程终止的标准已经失效,基于数值计算中牛顿迭代法的终止准则,设计了新的终止判断标准;然后提出基于线性方程组求解的限界模型检测算法;最后,通过3个测试用例说明,概率计算树逻辑限界模型检测方法在反例较短的情况下能够快速完成检测过程,而且比概率计算树逻辑的无界模型检测算法所需求得的状态空间要少.     

Mathematical logic and quantum finite state automata

This paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.     

Engineering constraint solvers for automatic analysis of probabilistic hybrid automata

In this article, we recall different approaches to the constraint-based, symbolic analysis of hybrid discrete-continuous systems and combine them to a technology able to address hybrid systems exhibiting both non-deterministic and probabilistic behavior akin to infinite-state Markov decision processes. To enable mechanized analysis of such systems, we extend the reasoning power of arithmetic satisfiability-modulo-theories (SMT) solving by, first, reasoning over ordinary differential equations (ODEs) and, second, a comprehensive treatment of randomized (also known as stochastic) quantification over discrete variables as well as existential quantification over both discrete and continuous variables within the mixed Boolean-arithmetic constraint system. This provides the technological basis for a constraint-based analysis of dense-time probabilistic hybrid automata, extending previous results addressing discrete-time automata [33]. Generalizing SMT-based bounded model-checking of hybrid automata [5], [31], stochastic SMT including ODEs permits the direct analysis of probabilistic bounded reachability problems of dense-time probabilistic hybrid automata without resorting to approximation by intermediate finite-state abstractions.     

Partial Order Reduction for Probabilistic Branching Time

In the past, partial order reduction has been used successfully to combat the state explosion problem in the context of model checking for non-probabilistic systems. For both linear time and branching time specifications, methods have been developed to apply partial order reduction in the context of model checking. Only recently, results were published that give criteria on applying partial order reduction for verifying quantitative linear time properties for probabilistic systems. This paper presents partial order reduction criteria for Markov decision processes and branching time properties, such as formulas of probabilistic computation tree logic. Moreover, we provide a comparison of the results established so far about reduction conditions for Markov decision processes.     

The SH-Verification Tool — Abstraction-Based Verification of Co-operating Systems

The sh-verification tool comprises computing abstractions of finite-state behaviour representations as well as automata and temporal logic based verification approaches. To be suitable for the verification of so called co-operating systems, a modified type of satisfaction relation (approximate satisfaction) is considered. Regarding abstraction, alphabetic language homomorphisms are used to compute abstract behaviours. To avoid loss of important information when moving to the abstract level, abstracting homomorphisms have to satisfy a certain property called simplicity on the concrete (i.e. not abstracted) behaviour. The well known state space explosion problem is tackled by a compositional method combined with a partial order method. Received March 1997 / Accepted in revised form July 1998     

Optimal transfer trees and distinguishing trees for testing observable nondeterministic finite-state machines

The fault-state detection approach for blackbox testing consists of two phases. The first is to bring the system under test (SUT) from its initial state to a targeted state t and the second is to check various specified properties of the SUT at t. This paper investigates the first phase for testing systems specified as observable nondeterministic finite-state machines with probabilistic and weighted transitions. This phase involves two steps. The first step transfers the SUT to some state t' and the second step identifies whether t' is indeed the targeted state t or not. State transfer is achieved by moving the SUT along one of the paths of a transfer tree (TT) and state identification is realized by using diagnosis trees (DT). A theoretical foundation for the existence and characterization of TT and DT with minimum weighted height or minimum average weight is presented. Algorithms for their computation are proposed.     

基于自动机的概率计算树逻辑验证方法

根据带有随机特征的复杂信息系统性质验证的需求,针对离散概率回报模型的分层直到公式,提出一种性质验证分析方法。在综合各种离散随机逻辑的基础上,使用一种同时具有迁移回报及迁移步区间表达能力的概率计算树逻辑表示系统模型的分层直到路径公式性质,使用自动机技术建模路径公式,通过构造积模型完成模型与自动机的同步演化,基于积模型给出相应的状态概率满足算法。实例结果验证了该方法的可行性和有效性。     

Quantitative and qualitative analysis of SysML activity diagrams

Model-driven engineering refers to a range of approaches that uses models throughout systems and software development life cycle. Towards sustaining such a successful approach in practice, we present a model-based verification framework that supports the quantitative and qualitative analysis of SysML activity diagrams. To this end, we propose an algorithm that maps SysML activity diagrams into Markov decision processes expressed using the language of the probabilistic symbolic model checker PRISM. Furthermore, we elaborate on the correctness of our translation algorithm by proving its soundness with respect to a SysML activity diagrams operational semantics that we also present in this work. The generated models can be verified against a set of properties expressed in the probabilistic computation tree logic. To automate our approach, we developed a prototype tool that interfaces a modeling environment and the probabilistic model checker. We also show how to leverage adversary generation to provide the developer with a useful counterexample/witness as a feedback on the verified properties. Finally, the established theoretical foundations are complemented with an illustrative case study that demonstrates the usability and benefit of such a framework.     

Probabilistic context-free grammars estimated from infinite distributions

In this paper, we consider probabilistic context-free grammars, a class of generative devices that has been successfully exploited in several applications of syntactic pattern matching, especially in statistical natural language parsing. We investigate the problem of training probabilistic context-free grammars on the basis of distributions defined over an infinite set of trees or an infinite set of sentences by minimizing the cross-entropy. This problem has applications in cases of context-free approximation of distributions generated by more expressive statistical models. We show several interesting theoretical properties of probabilistic context-free grammars that are estimated in this way, including the previously unknown equivalence between the grammar cross-entropy with the input distribution and the so-called derivational entropy of the grammar itself. We discuss important consequences of these results involving the standard application of the maximum-likelihood estimator on finite tree and sentence samples, as well as other finite-state models such as hidden Markov models and probabilistic finite automata.     

Model checking for a probabilistic branching time logic with fairness

We consider concurrent probabilistic systems, based on probabilistic automata of Segala & Lynch [55], which allow non-deterministic choice between probability distributions. These systems can be decomposed into a collection of “computation trees” which arise by resolving the non-deterministic, but not probabilistic, choices. The presence of non-determinism means that certain liveness properties cannot be established unless fairness is assumed. We introduce a probabilistic branching time logic PBTL, based on the logic TPCTL of Hansson [30] and the logic PCTL of [55], resp. pCTL [14]. The formulas of the logic express properties such as “every request is eventually granted with probability at least p”. We give three interpretations for PBTL on concurrent probabilistic processes: the first is standard, while in the remaining two interpretations the branching time quantifiers are taken to range over a certain kind of fair computation trees. We then present a model checking algorithm for verifying whether a concurrent probabilistic process satisfies a PBTL formula assuming fairness constraints. We also propose adaptations of existing model checking algorithms for pCTL [4, 14] to obtain procedures for PBTL under fairness constraints. The techniques developed in this paper have applications in automatic verification of randomized distributed systems. Received: June 1997 / Accepted: May 1998     

Reliability-aware automatic composition approach for web services

In this paper,we study the reliability-aware synthesis problem for composing available services automatically and guaranteeing that the composed result satisfies the specification,such as temporal constraints of functionality and reliability,centered on a synthesis model for mediator of web services composition (CSM).This approach focuses on handling attributes and state relations,and permitting users and services to operate over them,i.e.,read /write their data values and compare them according to a dense state order.We show that the reliability-aware synthesis problem for the specification is EXPTIME-complete and we give an exponential-time algorithm (CSM-NSA) which for a given formula ψ and a synthesis model,synthesizes available services in the library satisfying ψ over the synthesis model (if they exist) or responds with "not satisfiable" (otherwise).The specification ψ is a fragment of PCTL (probabilistic computation tree logic),obtained from "ordinary" CTL (computation tree logic) by replacing the EX,AX,EU and AU operation with their quantitative counterparts X >p,X =1,U >p,and U =1,respectively.As opposed to NSA,we provide a more effective algorithm to replace the NSA algorithm called CSM-HSA (heuristic synthesis algorithm).Though HSA is an incomplete algorithm,the answer is correct.The experiments show that the HSA algorithm solves the problem of reliability-aware service synthesis effectively and efficiently.     

A tableau-based decision procedure for CTL*

We present a sound, complete and implementable tableau method for deciding satisfiability of formulas in the propositional version of computation tree logic CTL*. This is the first such tableau. CTL* is an exceptionally important temporal logic with applications from hardware design to agent reasoning, but there is no easily automated reasoning approach to CTL*. The tableau here is a traditional tree-shaped or top-down style tableau, and affords the possibility of reasonably quick decisions on the satisfiability of medium-sized formulas and construction of small models for them. A straightforward subroutine is given for determining when looping allows successful branch termination, but much needed further development is left as future work. In particular, a more general repetition prevention mechanism is needed to speed up the task of tableau construction.     

非确定性环境中移动机器人避障策略的验证 ——基于形式化建模和概率分析

针对存在制动机误差和传感器噪声等因素的移动机器人,提出采用概率模型检测的方法对非确定性环境中移动机器人的避障策略进行验证和定量分析。首先将移动机器人的避障运动和动态障碍物的不确定性运动建模为马尔可夫决策过程。然后运用概率计算树逻辑语言描述移动机器人运动的关键属性并使用概率模型检测工具对其进行验证。最后分析得到移动机器人成功避障所花费的避碰时间,移动机器人到达目标位置所需要的时间和能量以及操作误差发生时的避碰时间对避障策略的影响,并使用MATLAB仿真验证成功避碰时间的正确性。     

Nondeterministic Control for Hybrid Search

Hybrid algorithms combining local and systematic search often use nondeterminism in fundamentally different ways. They may differ in the strategy to explore the search tree and/or in how computation states are represented. This paper presents nondeterministic control structures to express a variety of hybrid search algorithms concisely and elegantly. These nondeterministic abstractions describe the search tree and are compiled in terms of first-class continuations. They are also parameterized by search controllers that are under user control and specify the state representation and the exploration strategy. The resulting search language is thus high-level, flexible, and directly extensible. The abstractions are illustrated on a jobshop scheduling algorithm that combines tabu search and a limited form of backtracking. Preliminary experimental results indicate that the control structures induce small, often negligible, overheads.     

Quantum probabilistically cloning and computation

In this article we make a review on the usefulness of probabilistically cloning and present examples of quantum computation tasks for which quantum cloning offers an advantage which cannot be matched by any approach that does not resort to it. In these quantum computations, one needs to distribute quantum information contained in states about which we have some partial information. To perform quantum computations, one uses state-dependent probabilistic quantum cloning procedure to distribute quantum information in the middle of a quantum computation. And we discuss the achievable efficiencies and the efficient quantum logic network for probabilistic cloning the quantum states used in implementing quantum computation tasks for which cloning provides enhancement in performance.     

Abstractions of Random Finite-State Machines

Suppose that M is a large, complex finite-state system (fsm), and we want to construct a smaller model of it. A way of doing so, independent of any special properties that M might have, is to partition its states, inputs, and outputs into classes, collectively referred to as an abstraction. Since abstractions map many fsms into a non-deterministic machine defining an indistinguishability class, given a particular M, an optimal abstraction will minimize the size of this class. Algorithms for constructing such abstractions have been investigated in previous work.In this paper we are interested in large fsms generated by some random procedure, and want to find abstractions that minimize the expected size of an indistinguishability class. We establish various theoretical properties of abstractions optimal in an average sense, and also investigate experimentally how their characteristics change with the parameters governing the structure of the random machines.     

使用模型检测解决概率布尔网络优化控制

系统生物学期望对复杂生物系统建立一个真实的、可计算的模型,以便于以系统的角度去理解生物系统的演变过程。在系统生物学中,一个重要的主题是通过外部的干预控制发展关于基因调控网络的控制理论,以作为未来基因治疗技术。目前,布尔网络及其扩展的概率布尔网络已经被广泛用于对基因调控网络进行建模。在控制问题的研究中,概率布尔控制网络的状态迁移本质上构成一条有限状态空间的离散时间马尔科夫决策过程。依据马尔科夫决策过程的理论,通过概率模型检测方法解决网络中有限范围优化控制问题和无限范围优化控制问题。针对带有随机干扰且上下文相关的概率布尔控制网络,使用概率模型检测器PRISM对其进行形式化建模,然后将两类优化控制问题描述为相应的时序逻辑公式,最后通过模型检测寻找出最优解。实验结果表明,提出的方法可以有效地用于生物网络的分析和优化控制。     

Compositional programming abstractions for mobile computing

Recent advances in wireless networking technology and the increasing demand for ubiquitous, mobile connectivity demonstrate the importance of providing reliable systems for managing the reconfiguration and disconnection of components. The design of such systems requires tools and techniques appropriate to the task. Many formal models of computation, including UNITY, are not adequate for expressing reconfiguration and disconnection and are, therefore, inappropriate vehicles for investigating the impact of mobility on the construction of modular and composable systems. Algebraic formalisms such as the π-calculus have been proposed for modeling mobility. This paper addresses the question of whether UNITY, a state-based formalism with a foundation in temporal logic, can be extended to address concurrent, mobile systems. In the process, we examine some new abstractions for communication among mobile components that express reconfiguration and disconnection and which can be composed in a modular fashion     

Minimization of mealy finite-state machines by internal states gluing

A problem of minimization of Mealy finite-state machines that is common in synthesizing digital devices on programmable logic devices is considered. The proposed approach uses an operation of gluing two states and represents the finite-state machine as a list of transitions. Cases when gluing two states generates wait states are described. Algorithms that minimize the number of internal states, the number of transitions and input variables of Mealy finite-state machines are given. The experimental results showed that when used to implement finite-state machines on programmable logic devices, the proposed method helps decrease the implementation cost 1.31 times on average and 3 times at best. Topical directions for further study of finite-state machines minimization methods are given.