Quadratic optimal control of stable systems through spectral factorization

We consider the infinite horizon quadratic cost minimization problem for a linear system with finitely many inputs and outputs. A common approach to treat a problem of this type is to construct a semigroup in an abstract state space, and to use infinite-dimensional control theory. However, this approach is less appealing in the case where there are discrete time delays in the impulse response, because such time delays force both the control operator and the observation operator to be unbounded at the same time. In order to be able to include this case we take an alternative approach. We work in an input-output framework, and reduce the problem to a symmetric Wiener-Hopf problem, that can be solved by means of a canonical factorization of the symbol. In a standard shift semigroup realization this amounts to factorizations of the Riccati operator and the feedback operator into convolution operators and projections. Our approach leads to a new significant discovery: in the case where the impulse response of the system contains discrete time delays, the standard Riccati equation is incorrect; to get the correct Riccati equation the feed-through matrix of the system must be partially replaced by the feed-through matrix of the spectral factor. This means that, before it is even possible to write down the correct Riccati equation, a spectral factorization problem must first be solved to find one of the weighting matrices in this equation.     

A normed space of genetic operators with applications to scalability issues

We define an abstract normed vector space where the genetic operators are elements. This is used to define the disturbance of the generational operator G as the distance between the crossover and mutation operator (combined) and the identity. This quantity appears in a bound on the variance of fixed-point populations, and in a bound on the force //v - G(v)// that applies to the optimal population v. When analyzed for the case of fixed-length binary strings, a connection is shown between these measures and the size of the search space. Guides for parameter settings are given, if population convergence is required as the string length tends to infinity.     

Well-posed systems—The LTI case and beyond

This survey is an introduction to well-posed linear time-invariant (LTI) systems for non-specialists. We recall the more general concept of a system node, classical and generalized solutions of system equations, criteria for well-posedness, the subclass of regular linear systems, some of the available linear feedback theory. Motivated by physical examples, we recall the concepts of impedance passive and scattering passive systems, conservative systems and systems with a special structure that belong to these classes. We illustrate this theory by examples of systems governed by heat and wave equations. We develop local and global well-posedness results for LTI systems with nonlinear (in particular, bilinear) feedback, by extracting the abstract idea behind various proofs in the literature. We apply these abstract results to derive well-posedness results for the Burgers and Navier–Stokes equations.     

Signatures: A language extension for improving type abstraction and subtype polymorphism in C++

C++ uses inheritance as a substitute for subtype polymorphism. We give examples where this makes the type system too inflexible. We then describe a conservative language extension that allows a programmer to define an abstract type hierarchy independent of any implementation hierarchies, to retroactively abstract over an implementation, and to decouple subtyping from inheritance. This extension gives the user more of the flexibility of dynamic typing while retaining the efficiency and security of static typing. With default implementations and views flexible mechanisms are provided for implementing an abstract type by different concrete class types. We first show how the language extension can be implemented in a preprocessor to a C++ compiler, and then detail and analyse the efficiency of an implementation we directly incorporated in the GNU C++ compiler.     

Generalizable safety annotations for specification of failure patterns

Components in programmable systems often exhibit patterns of failure that are independent of function or system context. In this paper, we show that it is possible to capture, and reuse where appropriate, such patterns for the purposes of system safety analysis. We describe a language that enables abstract specification of failure behaviour and define the syntax and semantics of this language. The language extends concepts originally defined in HiP‐HOPS, a technique that enables a largely automated form of compositional system safety analysis. The paper describes how this language can be used to describe component failure patterns and demonstrates how it can be applied using a simple fuel system example. The approach is evaluated on a set of retrospective industrial case studies, where data‐mining and reverse engineering techniques are applied in order to identify hidden patterns in legacy safety analyses. Results show clear potential for practical use of patterns in HiP‐HOPS. We argue that careful specification and reuse of failure patterns in conjunction with a tool that automates Fault Tree and Failure Modes and Effects Analysis can help to simplify complex safety assessments. Copyright © 2010 John Wiley & Sons, Ltd.     

Abstract processes of place/transition systems

A well-known problem in Petri net theory is to formalise an appropriate causality-based concept of process or run for place/transition systems. The so-called individual token interpretation, where tokens are distinguished according to their causal history, giving rise to the processes of Goltz and Reisig, is often considered too detailed. The problem of defining a fully satisfying more abstract concept of process for general place/transition systems has so-far not been solved. In this paper, we recall the proposal of defining an abstract notion of process, here called BD-process, in terms of equivalence classes of Goltz-Reisig processes, using an equivalence proposed by Best and Devillers. It yields a fully satisfying solution for at least all one-safe nets. However, for certain nets which intuitively have different conflicting behaviours, it yields only one maximal abstract process. Here we identify a class of place/transition systems, called structural conflict nets, where conflict and concurrency due to token multiplicity are clearly separated. We show that, in the case of structural conflict nets, the equivalence proposed by Best and Devillers yields a unique maximal abstract process only for conflict-free nets. Thereby BD-processes constitute a simple and fully satisfying solution in the class of structural conflict nets.     

A functional correspondence between call-by-need evaluators and lazy abstract machines

We bridge the gap between compositional evaluators and abstract machines for the lambda-calculus, using closure conversion, transformation into continuation-passing style, and defunctionalization of continuations. This article is a followup of our article at PPDP 2003, where we consider call by name and call by value. Here, however, we consider call by need.We derive a lazy abstract machine from an ordinary call-by-need evaluator that threads a heap of updatable cells. In this resulting abstract machine, the continuation fragment for updating a heap cell naturally appears as an ‘update marker’, an implementation technique that was invented for the Three Instruction Machine and subsequently used to construct lazy variants of Krivine's abstract machine. Tuning the evaluator leads to other implementation techniques such as unboxed values. The correctness of the resulting abstract machines is a corollary of the correctness of the original evaluators and of the program transformations used in the derivation.     

Flocking behaviour in simple ecosystems as a result of artificial evolution

In this paper the FLOCK system is presented, which was designed to test the ability of simple genetic algorithm to evolve flocking behaviour in ecosystems consisting of plants, herbivores and predators. Open-ended evolution was applied in the experiments, first. Many different behaviours were observed, which were very similar to those in nature, for instance: the escape of herbivore from predators, making herbivores route towards plants or a pursuit of predators after herbivores. Another interesting behaviour was grouping of predators around plants, where the probability of meeting herbivores is greater than in other places. But open-ended evolution and complex vision system of animal were not sufficient to observe flocking behaviour. The advanced behaviour such as creation of flocks appeared as a result of steered evolution.     

A population dynamics approach for the water distribution problem

The water distribution system (WDS) is composed of several elements, where flow control is one of the most important components needed in order to provide a satisfactory level of service. In order to achieve an adequate level of water in the distribution tanks, we need to dynamically control the flow. Here, we propose a population dynamics approach in order to control tanks, by allocating in them the maximum uniform volume. The feedback interconnected systems reach a stable equilibrium point for both approaches presented (i.e. replicator and supply dynamics), and more specific an asymptotically stable equilibrium point for the replicator dynamics case. The stability analysis uses some passivity concepts and classic Lyapunov theory for a closed-loop system that combines the population dynamics (controller), and the WDS (process). We show via simulations the operation under different scenarios.     

Decentralized Control of Infinite Systems

We propose algorithms for the synthesis of decentralized state-feedback controllers with partial observation of infinite state systems, which are modeled by Symbolic Transition Systems. We first consider the computation of safe controllers ensuring the avoidance of a set of forbidden states and then extend this result to the deadlock free case. The termination of the algorithms solving these problems is ensured by the use of abstract interpretation techniques, but at the price of overapproximations, in particular, in the computation of the states which must be avoided. We then extend our algorithms to the case where the system to be controlled is given by a collection of subsystems (modules). This structure is exploited to locally compute a controller for each module. Our tool SMACS gives an empirical evaluation of our methods by showing their feasibility, usability and efficiency.     

Refinement preserving approximations for the design and verification of heterogeneous systems

Embedded systems are electronic devices that function in the context of a real environment, by sensing and reacting to a set of stimuli. Because of their close interaction with the environment, and to simplify their design, different parts of an embedded system are best described using different notations and different techniques. In this case, we say that the system is heterogeneous. We informally refer to the notation and the rules that are used to specify and verify the elements of heterogeneous systems and their collective behavior as a model of computation. In this paper, we consider different classes of relationships between models of computation and discuss their preservation properties with respect to the model's refinement relation and composition operator. In particular, we focus on abstraction and refinement relationships in the form of abstract interpretations and introduce the notion of conservative approximation. We show that, unlike abstract interpretations, conservative approximations preserve refinement verification results from an abstract to a concrete model while avoiding false positives. We also characterize the relationship between abstract interpretations and conservative approximations, and derive necessary and sufficient conditions to obtain a conservative approximation from a pair of abstract interpretations. In addition, we use the inverse of a conservative approximation to identify components that can be used indifferently in several models, thus enabling reuse across models of computation. The concepts described in this paper are illustrated with examples from continuous time and discrete time models of computation.     

Requirements engineering for e-business advantage

As a means of contributing to the achievement of business advantage for companies engaging in e-business, we propose a requirements engineering framework that incorporates a business strategy dimension. We employ Jackson’s Problem Frames approach, goal modeling, and business process modeling (BPM) to achieve this. Jackson’s context diagrams, used to represent business model context, are integrated with goal models to describe the requirements of the business strategy. We leverage the paradigm of projection in both approaches as a means of simultaneously decomposing both the requirement and context parts, from an abstract business level to concrete system requirements. Our approach maintains traceability to high-level business objectives via contribution relationship links in the goal model. We integrate use of role activity diagrams to describe business processes in detail where needed. The feasibility of our approach is shown by a well-known case study taken from the literature.     

Computing by observing: Simple systems and simple observers

We survey and extend the work on the paradigm called “computing by observing”. Its central feature is that one considers the behavior of an evolving system as the result of a computation. To this purpose an external observer records this behavior. In this way, several computational trade-offs between the observer and the observed system can be determined. It has turned out that the observed behavior of computationally simple systems can be very complex, when an appropriate observer is used. For example, a restricted version of context-free grammars with regular observers suffices to obtain computational completeness. As a second instantiation presented here, we apply an observer to sticker systems, an abstract model of DNA computing. Finally, we introduce and investigate the case where the observers can read only one measure of the observed system (e.g., mass or temperature), modeling in this way the limitations in the observation of real physical systems. Finally, a research perspective on the topic is presented.     

Combining ethnography and object-orientation for mobile interaction design: Contextual richness and abstract models

There has been a lot of interest in ethnography within human–computer interaction over the last two decades, and its relevance within systems development is today beyond question. However, one of the challenges reported is that ethnography generates findings and knowledge with such contextual richness that it can be hard to transfer into system design. In the light of recent years' push for the use of ethnography within the area of mobile human–computer interaction, this challenge has resurfaced and is of renewed importance to the research field. In this article we describe an interdisciplinary combination of ethnography with a structured software engineering method supporting the transition from collected data to design and implementation. We explore this combination through two case studies of mobile system development for supporting distributed work activities within industrial process control. We show that when developing mobile systems ethnographic data is a highly valuable source of input for developing object-oriented models by providing contextual richness, and that in turn, objected-oriented analysis is a highly valuable method for working with ethnographic field data in systems development by supporting the creation of abstract models. Combining the two, we have a method where ethnographic field studies inform core system design.     

A simple method for simulating biochemical reaction networks

We propose a simple method of simulating chemical reaction networks by using a multiset rewriting system: abstract rewriting system on multisets (ARMS). We simulate the oregonator model, a mathematical model of the Belousov-Zhabotinskii reaction, and we obtain the same behavior when the differential equations or the Gillespie method are used. We also compose a 1- and 2-dimensional cellular automata by using ARMS, and confirm that it shows the pattern forming that is observed in the BZ reaction. This work was presented in part at the First European Workshop on Artificial Life and Robotics, Vienna, Austria, July 12–13, 2007     

DESIGNING PROTOCOLS FOR ABDUCTIVE HYPOTHESIS REFINEMENT IN DYNAMIC MULTIAGENT ENVIRONMENTS

This paper studies multiagent systems where each agent has access to local observations of a dynamic environment and needs to build from this partial information an hypothesis on the state of the system. Each agent ensures that its hypothesis is consistent with its observations, and communicates with other agents to refine this hypothesis by confronting them to their own views. However, these communications are restricted by temporal and topological constraints, and can only be bilateral. We first study in this paper an abstract model of this problem, identifying conditions under which satisfying states can (or will) be reached. We rely in particular on a compositional consistency relation. We then detail a case study involving agents able to reason abductively (with Theorist), and study how demanding are the conditions required in this context. Different bilateral protocols are finally introduced and formally studied, to account for both compositional and noncompositional settings.     

Non-Standard Semantics for Program Slicing

In this paper we generalize the notion of compositional semantics to cope with transfinite reductions of a transition system. Standard denotational and predicate transformer semantics, even though compositional, provide inadequate models for some known program manipulation techniques. We are interested in the systematic design of extended compositional semantics, observing possible transfinite computations, i.e. computations that may occur after a given number of infinite loops. This generalization is necessary to deal with program manipulation techniques modifying the termination status of programs, such as program slicing. We include the transfinite generalization of semantics in the hierarchy developed in 1997 by P. Cousot, where semantics at different levels of abstraction are related with each other by abstract interpretation. We prove that a specular hierarchy of non-standard semantics modeling transfinite computations of programs can be specifiedin such a way that the standard hierarchy can be derived by abstract interpretation. We prove that non-standard transfinite denotational and predicate transformer semantics can be both systematically derived as solutions of simple abstract domain equations involving the basic operation of reduced power of abstract domains. This allows us to prove the optimality of these semantics, i.e. they are the most abstract semantics in the hierarchy which are compositional and observe respectively the terminating and initial states of transfinite computations, providing an adequate mathematical model for program manipulation.     

Abstract interpretation based verification of temporal properties for BioAmbients

This paper concerns the application of formal methods to biological systems, modeled specifically in BioAmbients, a variant of the Mobile Ambients calculus. Following the semantic-based approach of abstract interpretation, we define a new static analysis that computes an abstract transition system. Our analysis has two main advantages with respect to the analyses appearing in the literature: (i) it is able to address temporal properties which are more general than invariant properties; (ii) it supports, by means of a particular labeling discipline, the validation of systems where several copies of an ambient may appear.We also design new weaker and more efficient analyses by means of simple widening operators.     

Toward the interpretation of non-constructive reasoning as non-monotonic learning

We study an abstract representation of the learning process, which we call learning sequence, aiming at a constructive interpretation of classical logical proofs, that we see as learning strategies, coming from Coquand’s game theoretic interpretation of classical logic. Inspired by Gold’s notion of limiting recursion and by the Limit-Computable Mathematics by Hayashi, we investigate the idea of learning in the limit in the general case, where both guess retraction and resumption are allowed. The main contribution is the characterization of the limits of non-monotonic learning sequences in terms of the extension relation between guesses.