Abstract Regular Tree Model Checking

Regular (tree) model checking (RMC) is a promising generic method for formal verification of infinite-state systems. It encodes configurations of systems as words or trees over a suitable alphabet, possibly infinite sets of configurations as finite word or tree automata, and operations of the systems being examined as finite word or tree transducers. The reachability set is then computed by a repeated application of the transducers on the automata representing the currently known set of reachable configurations. In order to facilitate termination of RMC, various acceleration schemas have been proposed. One of them is a combination of RMC with the abstract-check-refine paradigm yielding the so-called abstract regular model checking (ARMC). ARMC has originally been proposed for word automata and transducers only and thus for dealing with systems with linear (or easily linearisable) structure. In this paper, we propose a generalisation of ARMC to the case of dealing with trees which arise naturally in a lot of modelling and verification contexts. In particular, we first propose abstractions of tree automata based on collapsing their states having an equal language of trees up to some bounded height. Then, we propose an abstraction based on collapsing states having a non-empty intersection (and thus “satisfying”) the same bottom-up tree “predicate” languages. Finally, we show on several examples that the methods we propose give us very encouraging verification results.     

Simulating perfect channels with probabilistic lossy channels

We consider the problem of deciding whether an infinite-state system (expressed as a Markov chain) satisfies a correctness property with probability 1. This problem is, of course, undecidable for general infinite-state systems. We focus our attention on the model of probabilistic lossy channel systems consisting of finite-state processes that communicate over unbounded lossy FIFO channels. Abdulla and Jonsson have shown that safety properties are decidable while progress properties are undecidable for non-probabilistic lossy channel systems. Under assumptions of “sufficiently high” probability of loss, Baier and Engelen have shown how to check whether a property holds of probabilistic lossy channel system with probability 1. In this paper, we consider a model of probabilistic lossy channel systems, where messages can be lost only during send transitions. In contrast to the model of Baier and Engelen, once a message is successfully sent to channel, it can only be removed through a transition which receives the message. We show that checking whether safety properties hold with probability 1 is undecidable for this model. Our proof depends upon simulating a perfect channel, with a high degree of confidence, using lossy channels.     

Verification of infinite-state dynamic systems using approximatequotient transition systems

This paper deals with computational methods for verifying properties of labeled infinite-state transition systems using quotient transition system (QTS). A QTS is a conservative approximation to the infinite-state transition system based on a finite partition of the infinite state space. For universal specifications, positive verification for a QTS implies the specification is true for the infinite-state transition system. We introduce the approximate QTS or AQTS. The paper presents a sufficient condition for an AQTS to be a bisimulation of the infinite state transition system. An AQTS bisimulation is essentially equivalent to the infinite-state system for the purposes of verification. It is well known, however, that finite-state bisimulations do not exist for most hybrid systems of practical interest. Therefore, the use of the AQTS for verification of universal specifications is proposed and illustrated with an example. This approach has been implemented in a tool for computer-aided verification of a general class of hybrid systems     

A “mixed” small gain and passivity theorem in the frequency domain

We show that the negative feedback interconnection of two causal, stable, linear time-invariant systems, with a “mixed” small gain and passivity property, is guaranteed to be finite-gain stable. This “mixed” small gain and passivity property refers to the characteristic that, at a particular frequency, systems in the feedback interconnection are either both “input and output strictly passive”; or both have “gain less than one”; or are both “input and output strictly passive” and simultaneously both have “gain less than one”. The “mixed” small gain and passivity property is described mathematically using the notion of dissipativity of systems, and finite-gain stability of the interconnection is proven via a stability result for dissipative interconnected systems.     

The boundedness of all products of a pair of matrices is undecidable

We show that the boundedness of the set of all products of a given pair Σ of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius ρ(Σ) is not computable because testing whether ρ(Σ)1 is an undecidable problem. As a consequence, the robust stability of linear systems under time-varying perturbations is undecidable, and the same is true for the stability of a simple class of hybrid systems. We also discuss some connections with the so-called “finiteness conjecture”. Our results are based on a simple reduction from the emptiness problem for probabilistic finite automata, which is known to be undecidable.     

Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time

We prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes and normed basic parallel processes (normed BPP). To the best of our knowledge, these are the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.     

Simulation Preorder over Simple Process Algebras

We consider the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones. First, we describe a general method how to utilize the decidability of bisimulation problems to solve (certain instances of) the corresponding simulation problems. For certain process classes, the method allows us to design effective reductions of simulation problems to their bisimulation counterparts and some new decidability results for simulation have already been obtained in this way. Then we establish the decidability border for the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones w.r.t. the hierarchy of process rewrite systems. In particular, we show that simulation preorder (in both directions) and simulation equivalence are decidable in EXPTIME between pushdown processes and finite-state ones. On the other hand, simulation preorder is undecidable between PA and finite-state processes in both directions. These results also hold for those PA and finite-state processes which are deterministic and normed, and thus immediately extend to trace preorder. Regularity (finiteness) w.r.t. simulation and trace equivalence is also shown to be undecidable for PA. Finally, we prove that simulation preorder (in both directions) and simulation equivalence are intractable between all classes of infinite-state systems (in the hierarchy of process rewrite systems) and finite-state ones. This result is obtained by showing that the problem whether a BPA (or BPP) process simulates a finite-state one is PSPACE-hard and the other direction is co -hard; consequently, simulation equivalence between BPA (or BPP) and finite-state processes is also co -hard.     

Remarks on nonlinear adaptive observer design

A solution to the problem of state estimation for systems with unknown parameters is to use some on-line adaptation of the observer parameters. On the basis of various existing results for such adaptive observer designs, a unifying “adaptive observer form” is proposed in this paper. This form indeed emphasizes properties allowing some asymptotic state estimation in spite of unknown parameters, as well as additional properties which further allow parameter estimation. As an example, it is shown how an adaptive observer can be designed for a class of state affine systems.     

Critical success factors revisited: success and failure cases of information systems for senior executives

The literature suggests the existence of critical success factors (CSFs) for the development of information systems that support senior executives. Our study of six organizations gives evidence for this notion of CSFs. The study further shows an interesting pattern, namely that companies either “get it right”, and essentially succeed on all CSFs, or “get it completely wrong”, that is, fall short on each of the CSFs. Among the six cases for which data were collected through in-depth interviews with company executives, three organizations seemed to manage all the CSFs properly, while two others managed all CSFs poorly. Only one organization showed a mixed scorecard, managing some factors well and some not so well. At the completion of the study, this organization could neither be judged as a success, nor as a failure. This dichotomy between success and failure cases suggests the existence of an even smaller set of “meta-success” factors. Based on our findings, we speculate that these “meta-success” factors are “championship”, “availability of resources”, and “link to organization objectives”.     

On uniform observation of nonuniformly observable systems

In [4,7,9,12], classes of nonlinear systems are considered for which observers can be designed. Although observability of nonlinear systems is known to be dependent on the input, the proposed observers have the property that the estimation error decays to zero irrespective of the input. In the first part of this paper, it is shown that this phenomenon follows from a common property of these systems: for all of them, the “unobservable states” with respect to some input, are in some sense “stable” (in the linear case, these systems are called detectable), and for this reason, a reduced order observer can be designed. In the second part is given a more general class of nonlinear systems for which such an observer can be designed.     

Cooperation without deliberation: A minimal behavior-based approach to multi-robot teams

While terminology and some concepts of behavior-based robotics have become widespread, the central ideas are often lost as researchers try to scale behavior to higher levels of complexity. “Hybrid systems” with model-based strategies that plan in terms of behaviors rather than simple actions have become common for higher-level behavior. We claim that a strict behavior-based approach can scale to higher levels of complexity than many robotics researchers assume, and that the resulting systems are in many cases more efficient and robust than those that rely on “classical AI” deliberative approaches. Our focus is on systems of cooperative autonomous robots in dynamic environments. We will discuss both claims that deliberation and explicit communication are necessary to cooperation and systems that cooperate only through environmental interaction. In this context we introduce three design principles for complex cooperative behavior—minimalism, statelessness and tolerance—and present a RoboCup soccer system that matches the sophistication of many deliberative soccer systems while exceeding their robustness, through the use of strict behavior-based techniques with no explicit communication.     

A modal specification theory for components with data

Modal specification is a well-known formalism used as an abstraction theory for transition systems. Modal specifications are transition systems equipped with two types of transitions: must-transitions that are mandatory to any implementation, and may-transitions that are optional. The duality of transitions allows for developing a unique approach for both logical and structural compositions, and eases the step-wise refinement process for building implementations. We propose Modal Specifications with Data (MSDs), the first modal specification theory with explicit representation of data. Our new theory includes the most commonly seen ingredients of a specification theory; that is parallel composition, conjunction and quotient. As MSDs are by nature potentially infinite-state systems, we propose symbolic representations based on effective predicates. Our theory serves as a new abstraction-based formalism for transition systems with data.     

Microcomputer selection process for organizational information management

This paper presents a selection model based on the Analytic Hierarchy Process (AHP). The methodology uses relevant organizational needs, required operational support categories, and respective attributes of the proposed systems in a selection hierarchy. Deriving a priority structure associated with this hierarchy permits the systematic comparison of candidate systems, and thereby selecting the one that best suits the organization. The application of this model to the selection of an accounting information system is described. The methodology outlined in this paper has been used in several large organizations (insurance and industrial corporations) for selection of their “standard micro” (or mini) computer systems. These systems were installed for various decentralized applications.     

Overrun handling approaches for overload-prone soft real-time systems

Traditional overrun handling approaches for real-time systems enforce some isolation property at the job or task level. This paper shows that by “relaxing” task isolation, it is possible to efficiently deal with overruns in soft real-time systems with highly variable task execution times and proposes Randomized Dropping (RD), a novel overrun handling mechanism. RD is able to bound task overruns in a probabilistic manner, thus providing “soft” task isolation. The paper shows how to combine RD with priority-driven and rate-based scheduling algorithms, and how to analyze the resulting system. Performance evaluation and comparison between simulation and analytical results are discussed.     

Counterexample-guided predicate abstraction of hybrid systems

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. The success of this approach depends on the choice of the predicates used for abstraction. In this paper, we focus on identifying these predicates automatically by analyzing spurious counterexamples generated by the search in the abstract state-space. We present the basic techniques for discovering new predicates that will rule out closely related spurious counterexamples, optimizations of these techniques, implementation of these in the verification tool, and case studies demonstrating the promise of the approach.     

A cognitivist model for decision support: COGITA project, a problem formulation assistant

The formulation of a problem may be defined as a process of acquisition and organization of knowledge related to a given situation, on which a decision maker projects some action. The assistance in the problem formulation that we may expect within decision support systems is difficult to design and to implement. This is mainly due to the frequent lack of attention to a sufficiently formalized conceptual framework which would consider the decision with a more cognition sciences oriented approach. In the first part, we will present an instrumental model for the study of decision processes as an attempt to simulate the cognitive process of knowledge acquisition and organization carried out by a decision maker facing a problematic situation. Considering its epistemological foundations, this model can be named “cognitivist model”. Within this model, the decision is defined as a cognitive construction which we call “decisional construct”. It consists of the elaboration of one or several abstract representations of the problematic situation (formulation phase), and the design of operational models (solving phase). In the second part, we will present the COGITA project, which consists of the design and realization of an environment for the development of problem formulation assistance systems. The modelization and simulation of cognitive processes call for relevant techniques originating either in artificial intelligence or in connectionism. We will show which are the main characteristics, potentials, limits and complementarity of these techniques and why their integration is fundamental and necessary to the simulation of the cognitive process associated with the formulation. COGITA is a hybrid system currently under development which tends to integrate symbolic artificial intelligence techniques and connectionist models in a cooperative hybridation the general architecture of which is presented.     

On the conservativeness of fuzzy and fuzzy-polynomial control of nonlinear systems

A fairly general class of nonlinear plants can be modeled as fuzzy systems, i.e., as a time-varying convex combination of “vertex” linear systems. As many linear LMI control results naturally generalize to such fuzzy systems, LMI formulations for fuzzy control became the tool of choice in the 1990s. Important results have since been obtained in the fuzzy arena, although significant sources of conservativeness remain. This paper reviews some of the sources of conservativeness of fuzzy control designs based on the linear vertex models instead of the original nonlinear equations. Then, ideas that may overcome some of the conservativeness issues (but increasing computational requirements) are discussed. Recently, the sum of squares paradigm extended some linear results to polynomial systems; this idea can be used for the so-called fuzzy polynomial systems that are also discussed in this work.     

Variable structure exponential stabilization of chained systems based on the extended nonholonomic integrator

In this paper, a new variable structure control strategy for exponentially stabilizing chained systems is presented based on the extended nonholonomic integrator model, the discontinuous coordinate transformation and the “reaching law method” in variable structure control design. The proposed approach converts the stabilization problem of an n-dimensional chained system into the pole-assignment problem of an (n−3)-dimensional linear time-invariant system and consequently simplifies the stabilization controller design of nonholonomic chained systems.     

Validating for Liveness in Hidden Adversary Systems

Multi-stream interactive systems can be seen as “hidden adversary” systems (HAS), where the observable behaviour on any interaction channel is affected by interactions happening on other channels. One way of modelling HAS is in the form of a multi-process I/O automata, where each interacting process appears as a token in a shared state space. Constraints in the state space specify how the dynamics of one process affects other processes. We define the “liveness criterion” of each process as the end objective to be achieved by the process. The problem now for each process is to achieve this objective in the face of unforeseen interferences from other processes. In an earlier paper, it was proposed that this uncertainty can be mitigated by collaboration among the disparate processes. Two types of collaboration philosophies were also suggested: altruistic collaboration and pragmatic collaboration. This paper addresses the HAS validation problem where processes collaborate altruistically.     

Continuity controlled hybrid automata

We investigate the connections between the process algebra for hybrid systems of Bergstra and Middelburg and the formalism of hybrid automata of Henzinger et al. We give interpretations of hybrid automata in the process algebra for hybrid systems and compare them with the standard interpretation of hybrid automata as timed transition systems. We also relate the synchronized product operator on hybrid automata to the parallel composition operator of the process algebra. It turns out that the formalism of hybrid automata matches a fragment of the process algebra for hybrid systems closely. We present an adaptation of the formalism of hybrid automata that yields an exact match.