Search

We present a new framework for the analysis of financial networks, called Actor-based Reactive Systems (ARS), that pushes further the Agent-Based approach (ABM) by resorting to ideas coming from the study of distributed systems in computer science. Two distinctive features, namely a fundamentally different management of time and a fully decentralized control logic, have a profound impact in terms of expressiveness of analysis, flexibility of modeling, and efficiency of experimentation. To illustrate the feasibility of the framework, we develop a realistic case study by analyzing the systemic risk of a model of the European banking network with a nontrivial contagion procedure, that combines an initial asset shock with the negative feedback loop triggered by asset fire sales. We show that, compared to ABMs, ARSs bring about finer-grained analyses, with a greater degree of heterogeneity and adaptivity of economic agents. Moreover, the very low computational cost and the detailed account of the system’s execution support the design and the development of very flexible stress tests to rapidly experiment with many hypothetical scenarios in a test-oriented style.

While several studies have linked network and in-fracture scale properties to conservative transport behavior in subsurface fractured media, studies on reactive transport cases remain relatively underdeveloped. In this study, we explore the behavior of an irreversible kinetic reaction during the interaction of two solute plumes, one consisting of species A and the other species B. When the plumes converge, these species react kinetically to form a new species C via $$A+B\xrightarrow {k} C$$ . This reactive system is studied using a three-dimensional discrete fracture network (DFN) model coupled with reactive Lagrangian particle tracking. We find that the interplay of network topology and chemical properties of the reactive solutes controls reactive transport processes. The network topology drives species A and B together, and the chemical properties dictate whether and how quickly a reaction occurs. Results demonstrate that reactions are most likely to occur in high-velocity fractures that make up the network backbone. The interplay between species’ chemical properties and transport is characterized by a non-dimensional Damkohler (Da) number. We show that the spatial distribution of reactions is sensitive to Da, which subsequently influences late-time tailing behavior in outlet breakthrough time distributions. The results of this study provide initial insights into how an irreversible reaction occurs during transport in a fracture network, using a methodology that can be applied to study reactive transport in a wide range of fractured media environments and contexts.

This paper investigates scheduling methods for two-stage real-time systems (2S-RTSs) that execute aperiodic tasks with firm and soft end-to-end deadlines. 2S-RTSs are often used to capture task execution in reactive systems where the first stage is responsible for detecting and preprocessing irregularly occurring external events and the second stage for taking certain actions to react to the identified situations. Since aperiodic tasks have no regular arrival patterns, it is more appropriate for such 2S-RTS to adopt an online scheduler to make scheduling decisions according to the current system state. We prove that the 2S-RTS scheduling problem is NP-hard, and present a novel share-based heuristic scheduling algorithm, referred to as HS-2S-RTS, to accomplish efficient online scheduling. Different from traditional optimal schedulers that aim to ensure all hard and soft deadline constraints, the goal of HS-2S-RTS consists of ensuring all firm deadline constraints and maximizing the minimum processor share assigned to soft tasks. Since the processor resource assigned to soft tasks is optimized without affecting firm deadline constraints, the schedulability of both firm and soft tasks can be improved. To reduce the actual run-time overhead, we further propose a quasi-shared-based scheduling algorithm, referred to as qHS-2S-RTS, that can achieve equivalent scheduling performance to HS-2S-RTS. We also design a new admission control algorithm for HS-2S-RTS and qHS-2S-RTS, called HSAC-2S-RTS. Simulation results validate our theoretical analysis that qHS-2S-RTS and HS-2S-RTS are able to satisfy all feasible firm deadline constraints while improving the schedulability of soft tasks.

The increasing complexity of reactive systems can be mitigated with the use of components and composition languages in model-driven engineering. Designing composition languages is a challenge itself as both practical applicability (support for different composition approaches in various application domains), and precise formal semantics (support for verification and code generation) have to be taken into account. In our Gamma Statechart Composition Framework, we designed and implemented a composition language for the synchronous, cascade synchronous and asynchronous composition of statechart-based reactive components. We formalized the semantics of this composition language that provides the basis for generating composition-related Java source code as well as mapping the composite system to a back-end model checker for formal verification and model-based test case generation. In this paper, we present the composition language with its formal semantics, putting special emphasis on design decisions related to the language and their effects on verifiability and applicability. Furthermore, we demonstrate the design and verification functionality of the composition framework by presenting case studies from the cyber-physical system domain.

During reactive transport modeling, the computing cost associated with chemical equilibrium calculations can be 10 to 10,000 times higher than that of fluid flow, heat transfer, and species transport computations. These calculations are performed at least once per mesh cell and once per time step, amounting to billions of them throughout the simulation employing high-resolution meshes. To radically reduce the computing cost of chemical equilibrium calculations (each requiring an iterative solution of a system of nonlinear equations), we consider an on-demand machine learning algorithm that enables quick and accurate prediction of new chemical equilibrium states using the results of previously solved chemical equilibrium problems within the same reactive transport simulation. The training operations occur on-demand, rather than before the start of the simulation when it is not clear how many training points are needed to accurately and reliably predict all possible chemical conditions that may occur during the simulation. Each on-demand training operation consists of fully solving the equilibrium problem and storing some key information about the just computed chemical equilibrium state (which is used subsequently to rapidly predict similar states whenever possible). We study the performance of the on-demand learning algorithm, which is mass conservative by construction, by applying it to a reactive transport modeling example and achieve a speed-up of one or two orders of magnitude (depending on the activity model used). The implementation and numerical tests are carried out in Reaktoro (reaktoro.org), a unified open-source framework for modeling chemically reactive systems.

In order to develop reliable software and systems, we depend on practical techniques for the construction and analysis of such software and systems. This special issue of Software Tools for Technology Transfer presents various tool-supported techniques that can help with the construction and analysis of such reliable software and systems. The papers in this special issue are extended versions of selected conference papers from the proceedings of the 24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2018).

Spatio-temporal events often describe the movements of an object in terms of space, time, and potential other attributes. Significant knowledge can be inferred by analysing them, either individually or atomically in form of trajectories. The trajectories can abstract additional properties and lead to deeper value. Moreover, external contextual information can be attributed to them to change their structure and lead to different perspectives. Because of this potentially valuable knowledge, nowadays indoor and outdoor tracking devices are used everywhere; generating countless events instantaneously. However, the extraction of knowledge from such heterogeneous, massive data is not a trivial task. In other terms, there is a need for a sophisticated system that is efficient in terms of distributed computing, failure handling, responsiveness, and abstraction. To answer this need, our study incorporates a fully fledged, reactive system for big trajectory data management. The system is unique of its kind because it is actor-based and features responsiveness, resiliency, and elasticity. Furthermore, our system is implemented using Scala; hence, we have the expressive power of both the Object-Oriented (OO) and Functional Programming (FP) paradigms. Allowing us to reach a higher level of abstraction to be able to process any trajectory type. The scope of this paper is to detail our system and discuss elasticity, routing strategies, load balancing, and our proper fault-tolerance mechanism. To fulfill this study, we consider the Geolife project’s GPS trajectory dataset.

Model-Based Testing (MBT) is a well-known technique that employs formal models to represent reactive systems’ behavior and generates test cases. Such systems have been specified and verified using mostly Finite State Machines (FSMs). There is a plethora of test generation algorithms in the literature; most of them are based on graphs once an FSM can be formally defined as a graph. Nevertheless, there is a lack of studies on analyzing cost and efficiency of FSM-based test generation algorithms. This study compares graph-based algorithms adopted to generate test cases from FSM models. In particular, we compare the Chinese Postman Problem (CPP) and H-Switch Cover (HSC) algorithms with the well-known Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms in the context of covering all-transitions and all-transition-pairs criteria in an FSM. First, a systematic literature mapping was conducted to summarize the methods that have been adopted in MBT, considering FSMs. Second, the main methods found were implemented and analyzed on randomly-generated FSMs, as well as real-world models that represent embedded systems of space applications. To make comparisons, we considered analyses in terms of cost (time), efficiency (mutant analysis) and characteristics of the generated test suites (number of test cases, average length of test cases, largest and smallest test cases, standard deviation and distribution of test cases). In general, CPP presented the best results in terms of number of test cases and test suite size. In addition, CPP also presented low distribution of average length compared to other algorithms.

Real-world PLC software is modular and composed of many different function blocks. Nevertheless, common approaches to PLC software verification do not leverage this but resort to inlining, or analyse instances of the same function block type independently. With the advent of constrained Horn clauses as the basis for automated program verification, many state-of-the-art verification procedures build upon them. We illustrate how this formalism allows for a uniform characterisation of PLC program semantics and safety goals, derived from reactive systems safety foundations. Furthermore, we give a natural extension of the resulting encoding which enables compositional reasoning about modular software. Due to the cyclic execution of PLCs, an engineer’s mental model of a single function block often exhibits state machine semantics – partitioning a block’s behaviour into different modes of operation. We illustrate how such a mode space, and similar high-level knowledge, can be integrated with our compositional characterisation. We investigate the impact of each technique on the model checking performance by characterising PLC software verification problems, both in a non-compositional and a compositional way that may incorporate mode transitions, and solving them with an SMT solver. Evaluation of our prototypical implementation on examples from the PLCopen Safety library shows the effectiveness of both the chosen formalism and using high-level summaries.

The synthesis of reactive systems from linear temporal logic (LTL) specifications is an important aspect in the design of reliable software and hardware. We present our adaption of the classic automata-theoretic approach to LTL synthesis, implemented in the tool Strix which has won the two last synthesis competitions (Syntcomp2018/2019). The presented approach is (1) structured, meaning that the states used in the construction have a semantic structure that is exploited in several ways, it performs a (2) forward exploration such that it often constructs only a small subset of the reachable states, and it is (3) incremental in the sense that it reuses results from previous inconclusive solution attempts. Further, we present and study different guiding heuristics that determine where to expand the on-demand constructed arena. Moreover, we show several techniques for extracting an implementation (Mealy machine or circuit) from the witness of the tree-automaton emptiness check. Lastly, the chosen constructions use a symbolic representation of the transition functions to reduce runtime and memory consumption. We evaluate the proposed techniques on the Syntcomp2019 benchmark set and show in more detail how the proposed techniques compare to the techniques implemented in other leading LTL synthesis tools.

The Epistemology Of Computer Simulation (EOCS) has developed as an epistemological and methodological analysis of simulative sciences using quantitative computational models to represent and predict empirical phenomena of interest. In this paper, Executable Cell Biology (ECB) and Agent-Based Modelling (ABM) are examined to show how one may take advantage of qualitative computational models to evaluate reachability properties of reactive systems. In contrast to the thesis, advanced by EOCS, that computational models are not adequate representations of the simulated empirical systems, it is shown how the representational adequacy of qualitative models is essential to evaluate reachability properties. Justification theory, if not playing an essential role in EOCS, is exhibited to be involved in the process of advancing and corroborating model-based hypotheses about empirical systems in ECB and ABM. Finally, the practice of evaluating model-based hypothesis by testing the simulated systems is shown to constitute an argument in favour of the thesis that computer simulations in ECB and ABM can be put on a par with scientific experiments.

Statecharts constitute an executable language for modelling event-based reactive systems. The essential complexity of statechart models solicits the need for advanced model testing and validation techniques. In this article, we propose a method aimed at enhancing statechart design with a range of techniques that have proven their usefulness to increase the quality and reliability of source code. The method is accompanied by a process that flexibly accommodates testing and validation techniques such as test-driven development, behaviour-driven development, design by contract, and property statecharts that check for violations of behavioural properties during statechart execution. The method is supported by the Sismic tool, an open-source statechart interpreter library in Python, which supports all the aforementioned techniques. Based on this tooling, we carry out a controlled user study to evaluate the feasibility, usefulness and adequacy of the proposed techniques for statechart testing and validation.

In the future, many teams of robots will navigate in home or office environments, similar to dense crowds operating currently in different scenarios. The paper aims to route a large number of robots so as to avoid build-up of congestions, similar to the problem of route planning of traffic systems. In this paper, first probabilistic roadmap approach is used to get a roadmap for online motion planning of robots. A graph search-based technique is used for motion planning. In the literature, typically the search algorithms consider only the static obstacles during this stage, which results in too many robots being scheduled on popular/shorter routes. The algorithm used here therefore penalizes roadmap edges that lie in regions with large robot densities so as to judiciously route the robots. This planning is done continuously to adapt the path to changing robotic densities. The search returns a deliberative trajectory to act as a guide for the navigation of the robot. A point at a distant of the deliberative path becomes the immediate goal of the reactive system. A ‘centre of area’-based reactive navigation technique is used to reactively avoid robots and other dynamic obstacles. In order to avoid two robots blocking each other and causing a deadlock, a deadlock avoidance scheme is designed that detects deadlocks, makes the robots wait for a random time and then allows them to make a few random steps. Experimental results show efficient navigation of a large number of robots. Further, routing results in effectively managing the robot densities so as to enable an efficient navigation.

Mean-payoff games (MPGs) are infinite duration two-player zero-sum games played on weighted graphs. Under the hypothesis of perfect information, they admit memoryless optimal strategies for both players and can be solved in Open image in new window . MPGs are suitable quantitative models for open reactive systems. However, in this context the assumption of perfect information is not always realistic. For the partial-observation case, the problem that asks if the first player has an observation-based winning strategy that enforces a given threshold on the mean-payoff, is undecidable. In this paper, we study the window mean-payoff objectives introduced recently as an alternative to the classical mean-payoff objectives. We show that, in sharp contrast to the classical mean-payoff objectives, some of the window mean-payoff objectives are decidable in games with partial-observation.

Reactive systems with a large degree of human interaction can be vulnerable to off-nominal behaviors (ONBs) that arise from the human operator’s unpredictability. In prior research, we have addressed the ONB problems by developing an approach to translating a set of reactive requirements into the rule-based causal component model (CCM). The CCM’s analysis involved expanding the CCM rules into a larger set of rules that encompass the system’s entire state space, displaying both nominal and off-nominal behaviors as transition paths. However, a major limitation of CCM is the potential for state explosion, which grows as a function of the system’s component states. In this paper, we introduce the causal scenario model (CSM), which uses the same rule-based approach, while addressing the state explosion problem associated with CCM. The CSM grows as a function of system components and provides a visually concise alternative to CCM, while still providing information useful in the exposing and addressing of ONBs during the requirements analysis phase. We introduce CSM and demonstrate the effectiveness of CSM, using a case study that would be more difficult to visualize using CCM, and most other state-based modeling techniques.

Currently, vertical partitioning has been used in multimedia databases in order to take advantage of its potential benefits in query optimization. Nevertheless, most vertical partitioning algorithms are static; this means that they optimize a vertical partitioning scheme (VPS) according to a workload, but if this workload suffers changes, the VPS may be degraded, which would result in long query response time. This paper presents a set of active rules to perform dynamic vertical partitioning in multimedia databases. First of all, these rules collect all the information that a vertical partitioning algorithm needs as input. Then, they evaluate this information in order to know if the database has experienced enough changes to trigger a performance evaluator. In this case, if the performance of the database falls below a threshold previously calculated by the rules, the vertical partitioning algorithm is triggered, which gets a new VPS. Finally, the rules materialize the new VPS. Our active rule base is implemented in the system DYMOND, which is an active rule-based system for dynamic vertical partitioning of multimedia databases. DYMOND's architecture and workflow are presented in this paper. Moreover, a case study is used to clarify and evaluate the functionality of our active rule base. Additionally, authors of this paper performed a qualitative evaluation with the aim of comparing and evaluating DYMOND's functionality. The results showed that DYMOND improved query performance in multimedia databases.

In biochemically reactive systems with small copy numbers of one or more reactant molecules, the dynamics is dominated by stochastic effects. To approximate those systems, discrete state-space and stochastic simulation approaches have been shown to be more relevant than continuous state-space and deterministic ones. In systems characterized by having simultaneously fast and slow timescales, existing discrete space-state stochastic path simulation methods, such as the stochastic simulation algorithm (SSA) and the explicit tau-leap (explicit-TL) method, can be very slow. Implicit approximations have been developed to improve numerical stability and provide efficient simulation algorithms for those systems. Here, we propose an efficient Multilevel Monte Carlo (MLMC) method in the spirit of the work by Anderson and Higham (SIAM Multiscal Model. Simul. 10(1), 2012). This method uses split-step implicit tau-leap (SSI-TL) at levels where the explicit-TL method is not applicable due to numerical stability issues. We present numerical examples that illustrate the performance of the proposed method.

Simulink and Stateflow (SL/SF) models are being widely used to design and develop embedded systems. Often the SL/SF models of embedded controllers turn out to be large and consist of many subsystems and hierarchies. When such a system is maintained, it becomes difficult to manually analyse the model to identify the impacted elements due to the existence of several explicit and implicit dependencies among the model elements. To automate the analysis of an SL/SF model, we propose a metamodel to capture various types of dependencies existing across the basic blocks. We have named this metamodel Simulink dependency graph (SLDG). We investigate the use of SLDG in change impact visualization and regression test selection. We have developed a prototype tool by implementing our approach for the aforementioned applications.

Modal transition systems (MTS) is a well-studied specification formalism of reactive systems supporting a step-wise refinement methodology. Despite its many advantages, the formalism as well as its currently known extensions are incapable of expressing some practically needed aspects in the refinement process like exclusive, conditional and persistent choices. We introduce a new model called parametric modal transition systems (PMTS) together with a general modal refinement notion that overcomes many of the limitations. We investigate the computational complexity of modal and thorough refinement checking on PMTS and its subclasses and provide a direct encoding of the modal refinement problem into quantified Boolean formulae, allowing us to employ state-of-the-art QBF solvers for modal refinement checking. The experiments we report on show that the feasibility of refinement checking is more influenced by the degree of nondeterminism rather than by the syntactic restrictions on the types of formulae allowed in the description of the PMTS.

In this paper we propose a logic-based, framework inspired by artificial intelligence, but scaled down for practical database and programming applications. Computation in the framework is viewed as the task of generating a sequence of state transitions, with the purpose of making an agent’s goals all true. States are represented by sets of atomic sentences (or facts), representing the values of program variables, tuples in a coordination language, facts in relational databases, or Herbrand models.

We analyze the efficacy of a standard manifold-based reduction method used to simplify reaction dynamics and find conditions under which the reduction can succeed and fail. In the standard reduction, a heteroclinic trajectory linking saddle and sink equilibria is taken as a candidate reduced manifold which we call a Canonical Invariant Manifold (CIM). We develop and exercise analytic tools for studying the local behavior of trajectories near the CIM. In so doing, we find conditions under which nearby trajectories are attracted to the CIM (ACIM) as well as conditions for which the dynamics on the ACIM are slow (SACIM). The method is demonstrated on a (1) simple model problem, (2) Zel’dovich mechanism for nitric oxide production, and (3) hydrogen–air system. For systems that evolve in a three-dimensional composition space, we find that normal stretching away from the CIM in a volume-shrinking vector field is admitted and that depending on the magnitude of the local rotation rate, may or may not render the CIM to be attractive. The success and failure of the candidate CIM as a SACIM is displayed for the model system. Results for the Zel’dovich mechanism and hydrogen–air systems are less definitive, though for specific conditions a SACIM is identified for both systems.

The goal of the RERS challenge is to evaluate the effectiveness of various verification and validation approaches on reactive systems, a class of systems that is highly relevant for industrial critical applications. The RERS challenge brings together researchers from different areas of software verification and validation, including static analysis, model checking, theorem proving, symbolic execution, and testing. The challenge provides a forum for experimental comparison of different techniques on specifically designed verification tasks. These benchmarks are automatically synthesized to exhibit chosen properties, and then enhanced to include dedicated dimensions of difficulty, such as conceptual complexity of the properties (e.g., reachability, safety, liveness), size of the reactive systems (a few hundred lines to millions of lines), and complexity of language features (arrays and pointer arithmetic). The STTT special section on RERS describes the results of the evaluations and the different analysis techniques that were used in the RERS challenges 2012 and 2013.

Game models are widely used to solve realizability, synthesis, and verification problems. This article considers an alternative approach to solving these problems on the basis of the concept of compatibility of automata (FSMs) or their logical specifications. The corresponding methods substantially differ from those used in the context of a game. It is shown how to use these methods for the synthesis of a winning strategy in a two-player game that does not relate to the development of reactive systems.

A novel, model-based test case generation approach for validating reactive systems, especially those supporting richly structured data inputs and/or interactions, is presented. Given an executable system model and an extended symbolic grammar specifying plausible system inputs, the approach performs a model-based simulation to (i) ensure the consistency of the model with respect to the specified inputs, and (ii) generate corresponding test cases for validating the system. The model-based simulation produces a state transition diagram (STD) automatically justifying the model runtime behaviors within the test case coverage. The STD can further be transformed to produce an evolved symbolic grammar, which can then be used to incrementally generate a refined set of test cases. As a case study, we present a live sequence chart (LSC) model-based test generator, named LCT in short, for LSC simulation and consistency testing. The evolved symbolic grammar produced by the simulator can either be used to generate practical test cases for software testing, or be further refined by applying our model-based test generation approach again with additional test coverage criteria. We further show that LSCs can also be used to specify and test certain temporal system properties during the model simulation. Their satisfaction, reflected in the STD, can either be served as a directive for selective test generation, or a basis for further temporal property model checking.

Multi-dimensional mean-payoff and energy games provide the mathematical foundation for the quantitative study of reactive systems, and play a central role in the emerging quantitative theory of verification and synthesis. In this work, we study the strategy synthesis problem for games with such multi-dimensional objectives along with a parity condition, a canonical way to express $\omega$-regular conditions. While in general, the winning strategies in such games may require infinite memory, for synthesis the most relevant problem is the construction of a finite-memory winning strategy (if one exists). Our main contributions are as follows. First, we show a tight exponential bound (matching upper and lower bounds) on the memory required for finite-memory winning strategies in both multi-dimensional mean-payoff and energy games along with parity objectives. This significantly improves the triple exponential upper bound for multi energy games (without parity) that could be derived from results in literature for games on VASS (vector addition systems with states). Second, we present an optimal symbolic and incremental algorithm to compute a finite-memory winning strategy (if one exists) in such games. Finally, we give a complete characterization of when finite memory of strategies can be traded off for randomness. In particular, we show that for one-dimension mean-payoff parity games, randomized memoryless strategies are as powerful as their pure finite-memory counterparts., Comment: Conference version published in CONCUR 2012, LNCS 7454. Journal version published in Acta Informatica, volume 51, issue 3-4, Springer, 2014

We present the BigMC tool for bigraphical reactive systems that may be instantiated as a verification tool for any formalism or domain-specific modelling language encoded as a bigraphical reactive system. We introduce the syntax and use of BigMC, and exemplify its use with two small examples: a textbook "philosophers" example, and an example motivated by a ubiquitous computing application. We give a tractable heuristic with which to approximate interference between reaction rules, and prove this analysis to be safe. We provide a mechanism for state reachability checking of bigraphical reactive systems, based upon properties expressed in terms of matching, and describe a checking algorithm that makes use of the causation heuristic.

International audience; Concurrent Constraint Programming (CCP) has been used over the last two decades as an elegant and expressive model for concurrent systems. It models systems of agents communicating by posting and querying partial information, represented as constraints over the variables of the system. This covers a vast variety of systems as those arising in biological phenomena, reactive systems, net- centric computing and the advent of social networks and cloud computing. In this paper we survey the main applications, developments and current trends of CCP.

Versatility, flexibility and robustness are essential requirements for software forensic tools. Researchers and practitioners need to put more effort into assessing this type of tool. A Markov model is a robust means for analyzing and anticipating the functioning of an advanced component based system. It is used, for instance, to analyze the reliability of the state machines of real time reactive systems. This research extends the architecture-based software reliability prediction model for computer forensic tools, which is based on Markov chains and COSMIC-FFP. Basically, every part of the computer forensic tool is linked to a discrete time Markov chain. If this can be done, then a probabilistic analysis by Markov chains can be performed to analyze the reliability of the components and of the whole tool. The purposes of the proposed reliability assessment method are to evaluate the tool's reliability in the early phases of its development, to improve the reliability assessment process for large computer forensic tools over time, and to compare alternative tool designs. The reliability analysis can assist designers in choosing the most reliable topology for the components, which can maximize the reliability of the tool and meet the expected reliability level specified by the end-user. The approach of assessing component-based tool reliability in the COSMIC-FFP context is illustrated with the Forensic Toolkit Imager case study.

This paper introduces the idea of reactive semantics and reactive Beth tableaux for modal logic and quotes some of its applications. The reactive idea is very simple. Given a system with states and the possibility of transitions moving from one state to another, we can naturally imagine a path beginning at an initial state and moving along the path following allowed transitions. If our starting point is s 0, and the path is s 0, s 1,..., s n , then the system is ordinary non-reactive system if the options available at s n (i.e., which states t we can go to from s n ) do not depend on the path s 0,..., s n (i.e., do not depend on how we got to s n ). Otherwise if there is such dependence then the system is reactive. It seems that the simple idea of taking existing systems and turning them reactive in certain ways, has many new applications. The purpose of this paper is to introduce reactive tableaux in particular and illustrate and present some of the applications of reactivity in general. Mathematically one can take a reactive system and turn it into an ordinary system by taking the paths as our new states. This is true but from the point of view of applications there is serious loss of information here as the applicability of the reactive system comes from the way the change occurs along the path. In any specific application, the states have meaning, the transitions have meaning and the paths have meaning. Therefore the changes in the system as we go along a path can have very important meaning in the context, which enhances the usability of the model.

We present a framework for the specification and verification of reactive concurrent programs using general-purpose mechanical theorem proving. We define specifications for concurrent programs by formalizing a notion of refinements analogous to stuttering trace containment. The formalization supports the definition of intuitive specifications of the intended behavior of a program. We present a collection of proof rules that can be effectively orchestrated by a theorem prover to reason about complex programs using refinements. The proof rules systematically reduce the correctness proof for a concurrent program to the definition and proof of an invariant. We include automated support for discharging this invariant proof with a predicate abstraction tool that leverages the existing theorems proven about the components of the concurrent programs. The framework is integrated with the ACL2 theorem prover and we demonstrate its use in the verification of several concurrent programs in ACL2.

The Teleo-Reactive approach designed by N. J. Nilsson offers a high-level programming model for the development of reactive systems such as robotic vehicles. Teleo-Reactive programs are written in a way that allows engineers to define behaviour taking account of goals and changes in the state of the environment. Since Nilsson's original definition, published in 1994, various researchers have used the Teleo-Reactive paradigm, either applied to a particular domain or extended by adding more capabilities to the original definition. This article provides a systematic literature review of 53 previous Teleo-Reactive-based studies in journals, conference proceedings and the like. The aim of this paper is to identify, appraise, select and synthesize all this high-quality research evidence relating to the use of the Teleo-Reactive paradigm. The literature has been systematically reviewed to offer an overview of the present state of this field of study and identify the principal results that have been obtained thanks to the Teleo-Reactive approach. Finally, this article details the challenges and difficulties that have to be overcome to ensure further advances in the use of this technique.

In the game-theoretic approach to the synthesis of reactive systems, specifications are often expressed as ω-regular languages. Computing a winning strategy to an infinite game whose winning condition is an ω-regular language is then the main step in obtaining an implementation. Conjoining all the properties of a specification to obtain a monolithic game suffers from the doubly exponential determinization that is required. Despite the success of symbolic algorithms, the monolithic approach is not practical. Existing techniques achieve efficiency by imposing restrictions on the ω-regular languages they deal with. In contrast, we present an approach that achieves improvement in performance through the decomposition of the problem while still accepting the full set of ω-regular languages. Each property is translated into a deterministic ω-regular automaton explicitly while the two-player game defined by the collection of automata is played symbolically. Safety and persistence properties usually make up the majority of a specification. We take advantage of this by solving the game incrementally. Each safety and persistence property is used to gradually construct the parity game. Optimizations are applied after each refinement of the graph. This process produces a compact symbolic encoding of the parity game. We then compose the remaining properties and solve one final game after possibly solving smaller games to further optimize the graph. An implementation is finally derived from the winning strategies computed. We compare the results of our tool to those of the synthesis tool Anzu.

A verifiable multiple UAV system cooperatively monitoring a road network is presented in this paper. The focus is on formal modelling and verification which can guarantee correctness of concurrent reactive systems such as multi-UAV systems. Kripke modelling is used to formally model the distributed cooperative control strategy, and to verify correctness of the specifications. Desirable properties of the mission such as liveness are specified in Computation Tree Logic (CTL). Model checking technique is used to exhaustively explore the state space to verify whether the system behaviour, modelled by Kripke model, satisfies the specifications. Violation of a specification is analysed by means of the counter-example generated by SMV model checking tool.

A core problem in formal methods is the transition from informal requirements to formal specifications. Especially when specifying the behavior of reactive systems, many formalisms require the user to either understand a complex mathematical theory and notation or to derive details not given in the requirements, such as the state space of the problem. For many approaches also a consistent set of requirements is needed, which enforces to resolve requirements conflicts prior to formalization. This paper describes a specification technique, where not states but signal patterns are the main elements. The notation is based on tables of regular expressions and supports a piece-wise formalization of potentially inconsistent requirements. Many properties, such as input completeness and consistency, can be checked automatically for these specifications. The detection and resolution of conflicts can be performed within our framework after formalization. Besides the formal foundation of our approach, this paper presents prototypical tool support and results from an industrial case study.

We present a rich and highly dynamic technique for analyzing, visualizing, and exploring the execution traces of reactive systems. The two inputs are a designer's inter-object scenario-based behavioral model, visually described using a UML2-compliant dialect of live sequence charts (LSC), and an execution trace of the system. Our method allows one to visualize, navigate through, and explore, the activation and progress of the scenarios as they "come to life" during execution. Thus, a concrete system's runtime is recorded and viewed through abstractions provided by behavioral models used for its design, tying the visualization and exploration of system execution traces to model-driven engineering. We support both event-based and real-time-based tracing, and use details-on-demand mechanisms, multi-scaling grids, and gradient coloring methods. Novel model exploration techniques include semantics-based navigation, filtering, and trace comparison. The ideas are implemented and tested in a prototype tool called the Tracer.

This paper introduces a face robot named ‘Buddy’ which can perform facial expressions, such as eye-tracking and lip synchronization, via movements of its facial elements (i.e., eyeballs, eyebrows, eyelids, and lips). Buddy has 14 degrees of freedom. To produce the realistic motion of Buddy, we built a ‘Reactive Behavior Decision Model’ which decides not only how to control the rotation angles and speed of facial elements, but to exhibit as well particular emotions that could express the robot’s personality. Buddy’s personality is formed in the model by the accumulated external stimuli and internal status. The process to automatically achieve reactive behavior in the model is classified into three steps: (1) to analyze the external stimuli and identify variations in Buddy’s internal status; (2) to decide the type and degree of emotion based on the robot’s personality; and (3) to generate specific facial expressions and gestures by combining the appropriate primitive behaviors chosen from emotion databases. By using this model, we have proven that Buddy can display various facial expressions and behaviors, at times very reasonable but quite unexpected.

Rebeca is an actor-based language with formal semantics which is suitable for modeling concurrent and distributed systems and protocols. Due to its object model, partial order and symmetry detection and reduction techniques can be efficiently applied to dynamic Rebeca models. We present two approaches for detecting symmetry in Rebeca models: One that detects symmetry in the topology of inter-connections among objects and another one which exploits specific data structures to reflect internal symmetry in the internal structure of an object. The former approach is novel in that it does not require any input from the modeler and can deal with the dynamic changes of topology. This approach is potentially applicable to a wide range of modeling languages for distributed and reactive systems. We have also developed a model checking tool that implements all of the above-mentioned techniques. The evaluation results show significant improvements in model size and model-checking time.

Virtual fixtures (VFs) can be defined as guiding constraints designed to enhance or assist human performance in a computer-controlled system by providing cues of haptic or audiovisual nature. In this paper we present a new characterization of VFs based on mechanics, and provide a set practical guidelines for the designers of such fixtures from a software architecture point of view. We propose an event-driven approach that facilitates the integration of these guiding constraints in a scene graphed-based environment. In this context some novel implementation of VFs are presented, where users may interact with a single or an assembled set of fixtures. We present two types of force attributes for VF and present their implications in a trajectory-following problem.

This paper presents the use of the B technique in its event based definition. We show that it is possible to encode, using Event B, the models (i.e., transition systems) associated to a process algebra with asynchronous semantics. The obtained Event B models consider that the Event B model associated to the left hand side of a BNF rule defining the algebra expressions is refined by a model corresponding to the right hand side of the same rule. The translation rules of each operator of a basic process algebra are given. Then, an example illustrating each translation rule is given. This approach is based on a proof technique and therefore it does not suffer from the state number explosion problem occurring in classical model checking. The interest of this work is the capability to validate user tasks or scenarios when using a given system and particularly a critical system. Finally, we discuss the application of this approach for validating user interfaces tasks in the human–computer interaction area.

A system of model equations coupling fluid flow, deformation of solid structure and chemical reactions is formulated starting from processes in biological tissue. The main aim of this paper is to analyse this non-standard system, where the elasticity modules are functionals of a concentration and the diffusion coefficients of the chemical substances are functions of their concentrations. A new approach and new methods are required and adapted to these nonlinearities and the transmission conditions on the interface solid–fluid. Strong solutions for the initial and boundary value problem are constructed under suitable regularity assumptions on the data, and stability estimates of the solutions with respect to the initial and boundary values are proved. These estimates imply uniqueness directly. The approach of the paper can be used in more general problems modeling reactive flow and transport and its interaction with elastic cell structures. In a forthcoming paper the approach of this paper is used for getting the upscaled system modeling reactive flow through biological tissue on the macroscopic scale, starting from a system on the cell level.

What do nanoscopic biomolecular complexes between the cells that line our blood vessels have in common with the microscopic silicate glass fiber optics that line our communication highways, or with the macroscopic steel rails that line our bridges? To be sure, these are diverse materials which have been developed and studied for years by distinct experimental and computational research communities. However, the macroscopic functional properties of each of these structurally complex materials pivots on a strong yet poorly understood interplay between applied mechanical states and local chemical reaction kinetics. As is the case for many multiscale material phenomena, this chemomechanical coupling can be abstracted through computational modeling and simulation to identify key unit processes of mechanically altered chemical reactions. In the modeling community, challenges in predicting the kinetics of such structurally complex materials are often attributed to the so-called rough energy landscape, though rigorous connection between this simple picture and observable properties is possible for only the simplest of structures and transition states. By recognizing the common effects of mechanical force on rare atomistic events ranging from molecular unbinding to hydrolytic atomic bond rupture, we can develop perspectives and tools to address the challenges of predicting macroscopic kinetic consequences in complex materials characterized by rough energy landscapes. Here, we discuss the effects of mechanical force on chemical reactivity for specific complex materials of interest, and indicate how such validated computational analysis can enable predictive design of complex materials in reactive environments.

L is a language for specifying properties of reactive systems. Such properties are considered as sets of words over the alphabet defined by a specification. Properties that correspond to complements of such sets are not expressible in the language L. An approach is proposed to constructing formulas of the language L that specify approximations of complements of sets defined in L.

Computer simulation of patient flow has been used extensively to assess the impacts of changes in the management of surgical care. However, little research is available on the utility of existing modeling techniques. The purpose of this paper is to examine the capacity of Statecharts, a system of graphical specification, for constructing a discrete-event simulation model of the peri-operative process. The Statecharts specification paradigm was originally developed for representing reactive systems by extending the formalism of finite-state machines through notions of hierarchy, parallelism, and event broadcasting. Hierarchy permits subordination between states so that one state may contain other states. Parallelism permits more than one state to be active at any given time. Broadcasting of events allows one state to detect changes in another state. In the context of the peri-operative process, hierarchy provides the means to describe steps within activities and to cluster related activities, parallelism provides the means to specify concurrent activities, and event broadcasting provides the means to trigger a series of actions in one activity according to transitions that occur in another activity. Combined with hierarchy and parallelism, event broadcasting offers a convenient way to describe the interaction of concurrent activities. We applied the Statecharts formalism to describe the progress of individual patients through surgical care as a series of asynchronous updates in patient records generated in reaction to events produced by parallel finite-state machines representing concurrent clinical and managerial activities. We conclude that Statecharts capture successfully the behavioral aspects of surgical care delivery by specifying permissible chronology of events, conditions, and actions.

Resource requirements and availability in heterogeneous networks may frequently vary over their lifetime; thus producing equally variant overloaded and under-loaded situations. Typical architectures cannot cope with the frequent availability fluctuation of reusable, non-replicable and highly dynamic resources (such as network capacity). This paper proposes an unstructured P2P overlay for sharing resources between underutilized and overloaded networks. Its aim is to satisfy the excessive resource demands of some networks by using free resources from others given the high failure rate and unstable availability of these resources in wide networks. We describe and analyze the proposed Capacity Sharing Overlay Architecture and show, with extensive simulations, its ability to provide remote underutilized capacity to underlying networks, even in the presence of high node failure rates, helping the networks to handle more user queries. Journal of Network and Systems Management

The paper analyzes the Electrical Manufacturing Services (EMS) industry’s current status in China, introduces a value stream mapping (VSM) collaboration tool which brings solid working process with agile information flow, and builds a theoretical foundation with a new management concept for China EMS to promote its integrated core competencies and to increase the market returns. VSM collaboration tools can be used across the electronics industry and other industries; it provides EMS the strategic advantages of a flexible, reactive system that agilely adapts to customers’ real-time needs, and builds EMS high profile with core competencies of being a strategic world-class performer.

Our goal is to understand the dynamics of neural computations in low-level vision. We study how the substrate of this system, that is local biochemical neural processes, could combine to give rise to an efficient and global perception. We will study these neural computations at different scales from the single-cell to the whole visual system to infer generic aspects of the under- lying neural code which may help to understand this cognitive ability. In fact, the architecture of cortical areas, such as the Primary Visual Cortex (V1), is massively parallel and we will focus on cortical columns as generic adaptive micro-circuits. To stress on the dynamical aspect of the processing, we will also focus on the transient response, that is during the first milliseconds after the presentation of a stimulus. In a generic model of a visual area, we propose to study the neural code as implementing visual pattern matching, that is as efficiently inverting a known model of image synthesis. A possible solution offered by the architecture of the visual pathways could be to represent at first on the surface of the cortical area how well the prototypical visual features are matched by a combination of inferential mechanisms as ideal observers. We studied the efficiency of this representation by rating the statistics of the output using natural scenes, that is scenes occurring frequently. We show that this may be finally used to provide a behavioral output such as an eye movement. However, constraints specific to the visual system imply that the set of prototypical features is not independent and that the cortical columns should communicate to produce an efficient, sparse solution. We will present efficient algorithms and representations based on the event-based nature of neural computations. By explicitely defining this efficiency, we propose then a simple implementation of Sparse Spike Coding using greedy inference mechanisms but also how the system may adapt in a unsupervised fashion. These computations may be implemented in simple models of neural networks by explicitly setting the lateral connectivity between populations of columns. Using natural scenes, this algorithm provides a model of V1 which exhibit prototypical properties of neural activities in that area. We show simple applications in the field of image processing as a quantitative method to evaluate these different cortical models.

International audience; The design of safety critical embedded systems has become a complex task, which requires both appropriate language features and efficient validation techniques. In this work, we propose the introduction of array iterators to the synchronous dataflow language Lustre as a mean to alleviate this complexity. We propose these new operators to provide Lustre programmers with a new mean for designing regular reactive systems. We study a compilation scheme that allows us to generate efficient loop imperative code from these iterators. This language aspect of our work has been fruitful since the iterators are being introduced in the industrial version of Lustre. Finally, we propose to take these regular structures into account during the validation process. This approach has already shown its applicability on different real-life case studies. The work we relate here is thus complete in the sense that our propositions at the language level are taken into account both at the compilation and the validation levels.

The model-driven architecture focuses on the evolution and integration of applications across heterogeneous platforms by means of generating implementations from platform-independent models. Most of the existing realizations of this idea are limited to static models. We propose a model-driven approach to the development of reactive information systems, like dynamic Web pages or Web services, modeling their typical request-query-update-response pattern by means of graph transformation rules. Rather than generating executable code from these models we focus on the verification of the consistency between different sub-models and an implementation that may have been produced manually. The main technical tool for achieving this goal is a mapping of graph transformation rules to contracts expressed in the Java Modeling Language.