This paper describes the development of finite abstractions of Max-Plus-Linear (MPL) systems using tropical operations. The idea of tropical abstraction is inspired by the fact that an MPL system is a discrete-event model updating its state with operations in the tropical algebra. The abstract model is a finite-state transition system: we show that the abstract states can be generated by operations on the tropical algebra, and that the generation of transitions can be established by tropical multiplications of matrices. The complexity of the algorithms based on tropical algebra is discussed and their performance is tested on a numerical benchmark against an existing alternative abstraction approach.
The notion of abstraction of an MPL system has been first discussed in @cite_4 . The procedure starts by transforming the MPL system characterised by @math into a PWA (piece-wise affine) model [Algorithm 2] Dieky1 , and then considering the partitions associated to the obtained PWA [Algorithm 6] Dieky1 . The abstract states associated to the partitions are represented by DBMs. The transitions are then generated using one-step forward-reachability analysis @cite_4 : first, the image of each abstract state w.r.t. the MPL system is computed; then, each image is intersected with partitions associated to other abstract states; finally, transition relations are defined for each non-empty intersection. This procedure is summarised in [Algorithm 7] Dieky1 .
@cite_4
2027649310
This work puts forward a novel technique to generate finite abstractions of autonomous and nonautonomous Max-Plus-Linear (MPL) models, a class of discrete-event systems used to characterize the dynamics of the timing related to successive events that synchronize autonomously. Nonautonomous versions of MPL models embed within their dynamics nondeterminism, namely a signal choice that is usually regarded as an exogenous control or schedule. In this paper, abstractions of MPL models are characterized as finite-state Labeled Transition Systems (LTS). LTS are obtained first by partitioning the state space (and, for the nonautonomous model, by covering the input space) of the MPL model and by associating states of the LTS to the introduced partitions, then by defining relations among the states of the LTS based on dynamical transitions between the corresponding partitions of the MPL state space, and finally by labeling the LTS edges according to the one-step timing properties of the events of the original MPL model. In order to establish formal equivalences, the finite abstractions are proven to either simulate or to bisimulate the original MPL model. This approach enables the study of general properties of the original MPL model by verifying (via model checking) equivalent logical specifications over the finite LTS abstraction. The computational aspects related to the abstraction procedure are thoroughly discussed and its performance is tested on a numerical benchmark. Max-Plus-Linear (MPL) systems are a class of discrete-event systems with a continuous state space characterizing the timing of the underlying sequential discrete events. These systems are predisposed to describe the timing synchronization between interleaved processes. MPL systems are employed in the analysis and scheduling of infrastructure networks, such as communication and railway systems, production and manufacturing lines, or biological systems. As a natural extension, Stochastic Max-Plus-Linear (SMPL) systems are MPL systems where the delays between successive events are characterized by random quantities. @PARASPLIT In practical applications SMPL systems are more realistic than simple MPL ones: for instance in a model for a railway network, train running times depend on driver behavior, on weather conditions, and on passenger numbers at stations. @PARASPLIT Verification is used to establish whether the system under consideration possesses certain properties expressed as formulae. As an example, reachability analysis is a fundamental problem in the area of formal methods, systems theory, and performance and dependability analysis. It is concerned with assessing whether a certain state of a system is attainable from given initial states of the system. @PARASPLIT Verification techniques and tools for finite-state systems have been widely investigated and developed in the past decades. However, if the system has a large number of states or even infinitely many states, in general we cannot apply such techniques directly. In this case we need to employ abstraction techniques to formally relate a concrete model to a finite abstraction of it, which is then amenable to be automatically verified by the relevant results in the literature. @PARASPLIT In this PhD thesis we develop novel abstraction techniques for MPL systems, and use them in an application to communication networks. Additionally we discuss reachability of MPL systems and abstraction techniques for SMPL systems. @PARASPLIT The abstraction and reachability algorithms for MPL systems developed in this thesis have been implemented as a MATLAB software tool, "Verification via biSimulations of MPL models'' (VeriSiMPL, as in "very simple''), which is freely available for download at http: www.sourceforge.net projects verisimpl . We use hybrid-systems techniques for the analysis of reachability properties of a class of piecewise-affine (PA) differential equations that are particularly suitable for the modeling of genetic regulatory networks. More specifically, we introduce a hyperrectangular partition of the state space that forms the basis for a discrete abstraction preserving the sign of the derivatives of the state variables. The resulting discrete transition system provides a qualitative description of the network dynamics that is well-adapted to available experimental data and that can be efficiently computed in a symbolic manner from inequality constraints on the parameters. Predicate abstraction has emerged to be a powerful technique for extracting finite-state models from infinite-state systems, and has been recently shown to enhance the effectiveness of the reachability computation techniques for hybrid systems. Given a hybrid system with linear dynamics and a set of linear predicates, the verifier performs an on-the-fly search of the finite discrete quotient whose states correspond to the truth assignments to the input predicates. To compute the transitions out of an abstract state, the tool needs to compute the set of discrete and continuous successors, and find out all the abstract states that this set intersects with. The complexity of this computation grows exponentially with the number of abstraction predicates. In this paper we present various optimizations that are aimed at speeding up the search in the abstract state-space, and demonstrate their benefits via case studies. We also discuss the completeness of the predicate abstraction technique for proving safety of hybrid systems. As model checking becomes increasingly used in industry, there is a big need for efficient new methods to deal with the large real-size designs. The author presents a novel method for improving the performance of model checking using parallelisation techniques. The model checking is performed on a distributed-memory environment consisting of a network of machines. The important two keys to focus on are the memory balance and communication reduction. A new algorithm for partitioning the large state space modelling industrial designs with hundreds of millions of states and transitions is proposed. The state space is supposed to be represented by a weighted Kripke structure (this is an extension of the Kripke structure where weights are associated with the states and with the transitions). This algorithm partitions the weighted Kripke structure by performing a combination of abstraction-partition-refinement on this structure. The CTL model checking algorithm is distributed on processes located on different network machines. Each one owns a partition and executes the algorithm on it. The algorithm for CTL model checking is designed to reduce the communication overhead between the processes. The experimental results on large real designs show that this method improves the quality of partitions, the communication overhead and then the overall performance of the model checking. Abstract We present non-extreme generalisations of intersecting p -brane solutions of eleven-dimensional supergravity which upon toroidal compactification reduce to non-extreme static black holes in dimensions D = 4, D = 5 and 6 ⩽ D ⩽ 9, parameterised by four, three and two charges, respectively. The D = 4 black holes are obtained either from a non-extreme configuration of three intersecting five-branes with a boost along the common string or from a non-extreme intersecting system of two two-branes and two five-branes. The D = 5 black holes arise from three intersecting two-branes or from a system of an intersecting two-brane and five-brane with a boost along the common string. The five-brane and two-brane with a boost along one direction reduce to black holes in D = 6 and D = 9, respectively, while a D = 7 black hole can be interpreted in terms of a non-extreme configuration of two intersecting two-branes. We discuss the expressions for the corresponding masses and entropies. Abstract In this paper we introduce and characterize the notion of approximate predictability for the general class of metric systems, which are a powerful modeling framework to deal with complex heterogeneous systems such as hybrid systems. Approximate predictability corresponds to the possibility of predicting the occurrence of specific states belonging to a particular subset of interest, in advance with respect to their occurrence, on the basis of observations corrupted by measurement errors. We establish a relation between approximate predictability of a given metric system and approximate predictability of a metric system that approximately simulates the given one. This relation allows checking approximate predictability of a system with an infinite number of states, provided that one is able to construct a metric system with a finite number of states and inputs, approximating the original one in the sense of approximate simulation. The analysis of approximate predictability of Piecewise Affine (PWA) systems is carried out as an application of the proposed approach. Coalgebra offers a unified theory of state based systems, including infinite streams, labelled transition systems and deterministic automata. In this paper, we use the coalgebraic view on systems to derive, in a uniform way, abstract procedures for checking behavioural equivalence in coalgebras, which perform (a combination of) minimization and determinization. First, we show that for coalgebras in categories equipped with factorization structures, there exists an abstract procedure for equivalence checking. Then, we consider coalgebras in categories without suitable factorization structures: under certain conditions, it is possible to apply the above procedure after transforming coalgebras with reflections. This transformation can be thought of as some kind of determinization. We will apply our theory to the following examples: conditional transition systems and (non-deterministic) automata. A practical real-time system for passive obstacle detection and avoidance is presented. Range information is obtained from stereo images by first computing a disparity picture from the image pair and extracting points above the ground plane. Then these points are projected onto the ground plane and an Instantaneous Obstacle Map (IOM) is obtained. The IOM is transformed into a one dimensional steering vector that represents the hindrance associated with steering in a particular direction and then a one dimensional search is performed on the steering vector for an angle with least hindrance. The steering direction and hindrance value are used to set the speed of the vehicle. This system has been implemented on the Mobile Perception Lab (MPL) at University of Massachusetts at Amherst with considerable success, running at 2 Hz for 256 spl times 240 sized images. > Abstract Documents in computer-readable form can be used to provide information about other documents, i.e. those they cite. To do this efficiently requires procedures for computer recognition of citing statements. This is not easy, especially for multi-sentence citing statements. Computer recognition procedures have been developed which are accurate to the following extent: 73 of the words in statements selected by computer procedures as being citing statements are words which are correctly attributable to the corresponding documents. The retrieval effectiveness of computer-recognized citing statements was tested in the following way. First, for eight retrieval requests in inorganiic chemistry, average recall by search of Chemical Abstracts Service indexing and Chemical Abstracts abstract text words was found to be 50 . Words from citing statements referring to the papers to be retrieved were then added to the index terms and abstract words as additional access points, and searching was repeated. Average recall increased to 70 . Only words from citing statements published within a year of the cited papers were used. The retrieval effect of citing statement words alone (published within a year) without index or abstract terms was the following: average recall was 40 . When just the words of the titles of the cited papers were added to those citing statement words, average recall increased to 50 . Abstraction can often lead to spurious counterexamples. Counterexample-guided abstraction refinement is a method of strengthening abstractions based on the analysis of these spurious counterexamples. For invariance properties, a counterexample is a finite trace that violates the invariant; it is spurious if it is possible in the abstraction but not in the original system. When proving termination or other liveness properties of infinite-state systems, a useful notion of spurious counterexamples has remained an open problem. For this reason, no counterexample-guided abstraction refinement algorithm was known for termination. In this paper, we address this problem and present the first known automatic counterexample-guided abstraction refinement algorithm for termination proofs. We exploit recent results on transition invariants and transition predicate abstraction. We identify two reasons for spuriousness: abstractions that are too coarse, and candidate transition invariants that are too strong. Our counterexample-guided abstraction refinement algorithm successively weakens candidate transition invariants and refines the abstraction. In this paper we introduce a model for a wide class of computational systems, whose behaviour can be described by certain rewriting rules. We gathered our inspiration both from the world of term rewriting, in particular from the rewriting logic framework Mes92 , and of concurrency theory: among the others, the structured operational semantics Plo81 , the context systems LX90 and the structured transition systems CM92 approaches. Our model recollects many properties of these sources: first, it provides a compositional way to describe both the states and the sequences of transitions performed by a given system, stressing their distributed nature. Second, a suitable notion of typed proof allows to take into account also those formalisms relying on the notions of synchronization and side-effects to determine the actual behaviour of a system. Finally, an equivalence relation over sequences of transitions is defined, equipping the system under analysis with a concurrent semantics, where each equivalence class denotes a family of computationally equivalent'''' behaviours, intended to correspond to the execution of the same set of (causally unrelated) events. As a further abstraction step, our model is conveniently represented using double-categories: its operational semantics is recovered with a free construction, by means of a suitable adjunction. Recently, we have improved the efficiency of the predicate abstraction scheme presented by Das, Dill and Park (1999). As a result, the number of validity checks needed to prove the necessary verification condition has been reduced. The key idea is to refine an approximate abstract transition relation based on the counter-example generated. The system starts with an approximate abstract transition relation on which the verification condition (in our case, this is a safety property) is model-checked. If the property holds then the proof is done; otherwise the model checker returns an abstract counter-example trace. This trace is used to refine the abstract transition relation if possible and start anew. At the end of the process, the system either proves the verification condition or comes up with an abstract counter-example trace which holds in the most accurate abstract transition relation possible (with the user-provided predicates as a basis). If the verification condition fails in the abstract system, then either the concrete system does not satisfy it or the abstraction predicates chosen are not strong enough. This algorithm has been used on a concurrent garbage collection algorithm and a secure contract-signing protocol. This method improved the performance on the first problem significantly, and allowed us to tackle the second problem, which the previous method could not handle. We consider the following problem: given a linear system and a linear temporal logic (LTL) formula over a set of linear predicates in its state variables, find a feedback control law with polyhedral bounds and a set of initial states so that all trajectories of the closed loop system satisfy the formula. Our solution to this problem consists of three main steps. First, we partition the state space in accordance with the predicates in the formula, and construct a transition system over the partition quotient, which captures our capability of designing controllers. Second, using a procedure resembling model checking, we determine runs of the transition system satisfying the formula. Third, we generate the control strategy. Illustrative examples are included. Weighted automata are a generalisation of non-deterministic automata where each transition, in addition to an input letter, has also a quantity expressing the weight (e.g. cost or probability) of its execution. As for non-deterministic automata, their behaviours can be expressed in terms of either (weighted) bisimilarity or (weighted) language equivalence. Coalgebras provide a categorical framework for the uniform study of state-based systems and their behaviours. In this work, we show that coalgebras can suitably model weighted automata in two different ways: coalgebras on Set (the category of sets and functions) characterise weighted bisimilarity, while coalgebras on Vect (the category of vector spaces and linear maps) characterise weighted language equivalence. Relying on the second characterisation, we show three different procedures for computing weighted language equivalence. The first one consists in a generalisation of the usual partition refinement algorithm for ordinary automata. The second one is the backward version of the first one. The third procedure relies on a syntactic representation of rational weighted languages. We consider verification of safety properties for concurrent real-timed systems modelled as timed Petri nets by performing symbolic forward reachability analysis. We introduce a formalism, called region generators, for representing sets of markings of timed Petri nets. Region generators characterize downward closed sets of regions and provide exact abstractions of sets of reachable states with respect to safety properties. We show that the standard operations needed for performing symbolic reachability analysis are computable for region generators. Since forward reachability analysis is necessarily incomplete, we introduce an acceleration technique to make the procedure terminate more often on practical examples. We have implemented a prototype for analyzing timed Petri nets and used it to verify a parameterized version of Fischer's protocol, Lynch and Shavit's mutual exclusion protocol and a producer-consumer protocol. We also used the tool to extract finite-state abstractions of these protocols. This document specifies the Multicast Protocol for Low-Power and Lossy Networks (MPL), which provides IPv6 multicast forwarding in constrained networks. MPL avoids the need to construct or maintain any multicast forwarding topology, disseminating messages to all MPL Forwarders in an MPL Domain. MPL has two modes of operation. One mode uses the Trickle algorithm to manage control-plane and data-plane message transmissions and is applicable for deployments with few multicast sources. The other mode uses classic flooding. By providing both modes and parameterization of the Trickle algorithm, an MPL implementation can be used in a variety of multicast deployments and can trade between dissemination latency and transmission efficiency. We present a novel approach for generalizing the IC3 algorithm for invariant checking from finite-state to infinite-state transition systems, expressed over some background theories. The procedure is based on a tight integration of IC3 with Implicit (predicate) Abstraction, a technique that expresses abstract transitions without computing explicitly the abstract system and is incremental with respect to the addition of predicates. In this scenario, IC3 operates only at the Boolean level of the abstract state space, discovering inductive clauses over the abstraction predicates. Theory reasoning is confined within the underlying SMT solver, and applied transparently when performing satisfiability checks. When the current abstraction allows for a spurious counterexample, it is refined by discovering and adding a sufficient set of new predicates. Importantly, this can be done in a completely incremental manner, without discarding the clauses found in the previous search. The paper presents an approach for shape analysis based on predicate abstraction. Using a predicate base that involves reachability relations between program variables pointing into the heap, we are able to analyze functional properties of programs with destructive heap updates, such as list reversal and various in-place list sorts. The approach allows verification of both safety and liveness properties. The abstraction we use does not require any abstract representation of the heap nodes (e.g. abstract shapes), only reachability relations between the program variables. The computation of the abstract transition relation is precise and automatic yet does not require the use of a theorem prover. Instead, we use a small model theorem to identify a truncated (small) finite-state version of the program whose abstraction is identical to the abstraction of the unbounded-heap version of the same program. The abstraction of the finite-state version is then computed by BDD techniques. For proving liveness properties, we augment the original system by a well-founded ranking function, which is abstracted together with the system. Well-foundedness is then abstracted into strong fairness (compassion). We show that, for a restricted class of programs that still includes many interesting cases, the small model theorem can be applied to this joint abstraction. Independently of the application to shape-analysis examples, we demonstrate the utility of the ranking abstraction method and its advantages over the direct use of ranking functions in a deductive verification of the same property. I. Introduction.- 1.1. General Remarks.- 1.2. The Robbins-Monro Process.- 1.3. A "Continuous" Process Version of Section 2.- 1.4. Regulation of a Dynamical System a simple example.- 1.5. Function Minimization: The Kiefer-Wolfowitz Procedure.- 1.6. Constrained Problems.- 1.7. An Economics Example.- II. Convergence w.p.1 for Unconstrained Systems.- 2.1. Preliminaries and Motivation.- 2.2. The Robbins-Monro and Kiefer-Wolfowitz Algorithms: Conditions and Discussion.- 2.3. Convergence Proofs for RM and KW-like Procedures.- 2.3.1. A Basic RM-like Procedure.- 2.3.2. One Dimensional RM and Accelerated RM Procedures.- 2.3.3. A Continuous Parameter RM Procedure.- 2.3.4. The Basic Kiefer-Wolfowitz Procedure.- 2.3.5. Random Directions KW Methods.- 2.4. A General Robbins-Monro Process: "Exogenous Noise".- 2.4.1. The Case of Bounded h(*,*).- 2.4.2. Unbounded h(*,*): Exogenous Noise.- 2.5. A General RM Process State Dependent Noise.- 2.5.1. Extensions and Localizations of Theorem 2.5.2.- 2.6. Some Applications.- 2.7. Mensov-Rademacher Estimates.- III. Weak Convergence of Probability Measures.- IV. Weak Convergence for Unconstrained Systems.- 4.1. Conditions and General Discussion.- 4.2. The Robbins-Monro and Kiefer-Wolfowitz Procedures.- 4.2.1. The Basic Robbins-Monro Procedure.- 4.2.2. The One-Dimensional Robbins-Monro Procedure.- 4.2.3. The Kiefer-Wolfowitz Procedure.- 4.2.4. A Case Where the Limit Satisfies a Generalized ODE.- 4.2.5. A Continuous Parameter KW Procedure.- 4.3. A General Robbins-Monro Process: Exogenous Noise.- 4.4. A General RM Process: State Dependent Noise.- 4.5. The Identification Problem.- 4.6. A Counter-Example to Tightness.- 4.7. Boundedness of Xn and Tightness of Xn(*) .- V. Convergence w.p.1 For Constrained Systems.- 5.1. A Penalty-Multiplier Algorithm for Equality Constraints.- 5.1.1. A Basic RM-like Algorithm, Conditions and Discussion.- 5.1.2. The Noise Condition, Discussion and Generalization.- 5.1.3. Boundedness of Xn .- 5.1.4. Proof of the Main Theorem.- 5.1.5. Constrained Function Minimization and Other Extensions.- 5.2. A Lagrangian Method for Inequality Constraints.- 5.2.1. The Algorithm and Conditions.- 5.2.2. The Convergence Theorem 18.- 5.2.3. A Non-Convergent but Useful Algorithm.- 5.2.4. An Application to the Identification Problem.- 5.3. A Projection Algorithm.- 5.4. A Penalty-Multiplier Method for Inequality Constraints.- VI. Weak Convergence: Constrained Systems.- 6.1. A Multiplier Type Algorithm for Equality Constraints.- 6.1.1. Boundedness of Xn .- 6.1.2. The Noise Condition, Discussion.- 6.1.3. The Convergence Theorem.- 6.2. The Lagrangian Method.- 6.3. A Projection Algorithm.- 6.4. A Penalty-Multiplier Algorithm for Inequality Constraints.- VII. Rates of Convergence.- 7.1. The Problem Formulation.- 7.2. Conditions and Discussions.- 7.3. Rates of Convergence for Case 1, the KW Algorithm.- 7.4. Discussion of Rates of Convergence for Two KW Algorithms.