Formal testing of timed graph transformation systems using metric temporal graph logic

Embedded real-time systems generate state sequences where time elapses between state changes. Ensuring that such systems adhere to a provided specification of admissible or desired behavior is essential. Formal model-based testing is often a suitable cost-effective approach. We introduce an extended version of the formalism of symbolic graphs, which encompasses types as well as attributes, for representing states of dynamic systems. Relying on this extension of symbolic graphs, we present a novel formalism of timed graph transformation systems (TGTSs) that supports the model-based development of dynamic real-time systems at an abstract level where possible state changes and delays are specified by graph transformation rules. We then introduce an extended form of the metric temporal graph logic (MTGL) with increased expressiveness to improve the applicability of MTGL for the specification of timed graph sequences generated by a TGTS. Based on the metric temporal operators of MTGL and its built-in graph binding mechanics, we express properties on the structure and attributes of graphs as well as on the occurrence of graphs over time that are related by their inner structure. We provide formal support for checking whether a single generated timed graph sequence adheres to a provided MTGL specification. Relying on this logical foundation, we develop a testing framework for TGTSs that are specified using MTGL. Lastly, we apply this testing framework to a running example by using our prototypical implementation in the tool AutoGraph.

     

Heterogeneous knowledge representation: integrating connectionist and symbolic computation

Heterogeneous knowledge representation allows combination of several knowledge representation techniques. For instance, connectionist and symbolic systems are two different computational paradigms and knowledge representations. Unfortunately, the integration of different paradigms and knowledge representations is not easy and very often is informal. In this paper, we propose a formal approach to integrate these two paradigms where as a symbolic system we consider a (logic) rule-based system. The integration is operated at language level between neural networks and rule languages. The formal model that allows the integration is based on constraint logic programming and provides an integrated framework to represent and process heterogeneous knowledge. In order to achieve this we define a new language that allows expression and modelling in a natural and intuitive way the above issues together with the operational semantics.     

Interruptibility as a constraint on hybrid systems

It is widely mooted that a plausible computational cognitive model should involve both symbolic and connectionist components. However, sound principles for combining these components within a hybrid system are currently lacking; the design of such systems is oftenad hoc. In an attempt to ameliorate this we provide a framework of types of hybrid systems and constraints therein, within which to explore the issues. In particular, we suggest the use of system independent constraints, whose source lies in general considerations about cognitive systems, rather than in particular technological or task-based considerations. We illustrate this through a detailed examination of an interruptibility constraint: handling interruptions is a fundamental facet of cognition in a dynamic world. Aspects of interruptions are delineated, as are their precise expression in symbolic and connectionist systems. We illustrate the interaction of the various constraints from interruptibility in the different types of hybrid systems. The picture that emerges of the relationship between the connectionist and the symbolic within a hybrid system provides for sufficient flexibility and complexity to suggest interesting general implications for cognition, thus vindicating the utility of the framework.     

Nuclear power plant communications in normative and actual practice: A field study of control room operators' communications

The safety and availability of sociotechnical critical systems still relies on human operators, both through human reliability and human ability to handle adequately unexpected events. In this article, the authors focus on ergonomic field studies of nuclear power plant control room operator activities, and more specifically on the analysis of communications within control room crews. They show how operators use vague and porous verbal exchanges to produce continuous, redundant, and diverse interactions to successfully construct and maintain individual and mutual awareness, which is paramount to achieve system stability and safety. Such continuous interactions enable the operators to prevent, detect, and reverse system errors or flaws by anticipation or regulation. This study helps in providing cues for the design of more workable systems for human cooperation in nuclear power plant operation. © 2007 Wiley Periodicals, Inc. Hum Factors Man 17: 43–78, 2007.     

Combination of convex theories: Modularity,deduction completeness,and explanation

Decision procedures are key components of theorem provers and constraint satisfaction systems. Their modular combination is of prime interest for building efficient systems, but their effective use is often limited by poor interface capabilities, when such procedures only provide a simple “sat/unsat” answer. In this paper, we develop a framework to design cooperation schemas between such procedures while maintaining modularity of their interfaces. First, we use the framework to specify and prove the correctness of classic combination schemas by Nelson–Oppen and Shostak. Second, we introduce the concept of deduction complete satisfiability procedures, we show how to build them for large classes of theories, then we provide a schema to modularly combine them. Third, we consider the problem of modularly constructing explanations for combinations by re-using available proof-producing procedures for the component theories.     

Symbolic Algorithmic Analysis of Rectangular Hybrid Systems

This paper investigates symbolic algorithmic analysis of rectangular hybrid systems.To deal with the symbolic reachability problem,a restricted constraint system called hybrid zone is formalized for the representation and manipulation of rectangular automata state-spaces.Hybrid zones are proved to be closed over symbolic reachability operations of rectangular hybrid systems.They are also applied to model-checking procedures for verifying some important classes of timed computation tree logic formulas.To ...     

Reference,Synthesis and Constraint Satisfaction*

In this paper we discuss two kinds of constraint satisfaction problems that arise in the context of geometric modelling, In particular in the modification of 2-D wire-frame diagrams that are subject to an arbitrary number of geometrical and topological constraints. We argue that problems in this domain can be classified in two categories that we shall call problems of reference and problems of synthesis. Since Sutherland's Sketchpad program [16], a large number of systems have addressed constraint satisfaction in terms of the representation of constraints sets as equation systems, which in turn are solved by numerical methods like local propagation, relaxation and Gaussian elimination. Here, we present an alternative framework. We argue that conceptualising constraint satisfaction as symbolic rather than “numerical” problems helps to clarify the notion of “constraint”, simplify solution methods, and to explain the intuitive inferential processes underlying the modification of drawings in the course of interactive drafting sessions. The theory presented in this paper has been tested with an experimental computer program called Graflog [5, 8, 9, 10, 11, 12]. The program has been implemented during the last four years, and has evolved through several stages. The current version is implemented in terms of two Unix-processes connected by Unix-pipes. The first is a “C” program running X windows, and handles the external aspects of the interaction. The second is a Prolog program supporting the representational structures and interpreters of the system.     

A unified symbolic evaluation framework for parallelizing compilers

The quality of many optimizations and analyses of parallelizing compilers depends significantly on the ability to evaluate symbolic expressions and on the amount of information available about program variables at arbitrary program points. In this paper, we describe an effective and unified symbolic evaluation framework that statically determines the values of variables and symbolic expressions, assumptions about and constraints between variable values, and the condition under which control flow reaches a program statement. We introduce the program context, a novel representation for comprehensive and compact control and data flow analysis information. Program contexts are described as first order logic formulas, which allows us to use public domain software for standard symbolic manipulation. Computations are represented as algebraic expressions defined over a program's problem size. Our symbolic evaluation techniques comprise accurate modeling of assignment and input/output statements, branches, loops, recurrences, arrays, and procedures. All of our techniques target both linear, as well as nonlinear, expressions and constraints. Efficiency of symbolic evaluation is highly improved by aggressive simplification techniques. A variety of examples, including program verification, dependence analysis, array privatization, communication vectorization, and elimination of redundant communication, are used to illustrate the effectiveness of our approach. We present results from a preliminary implementation of our framework, which is used as part of a parallelizing compiler that demonstrates the potential performance gains achievable by employing symbolic evaluation to support program parallelization.     

Failure-based equivalence of constraint automata

Constraint automata are the first-proposed operational semantics of Reo coordination language. They can be composed not only by all well-defined composition operators of labeled transition systems but also by two new operators. The new operators are joining of constraint automata with respect to their common port names and hiding a port name in all transition labels. The operations of these two extra operators depend on the internal structures of the transition labels, while in the others each transition label is considered as a simple entity. An equivalence relation between transition systems is a congruence relation if the replacement of the components of a model by the equivalent ones always yields a model that is equivalent with the original one. Obviously, this definition of the congruency depends on the operators which are used to compose the components of models. This paper introduces four congruency results: we prove that failure-based equivalence relation CFFD (chaos-free failures divergences relation) is a congruence relation with respect to joining of constraint automata and also with respect to hiding port names in a constraint automaton. We also show that these are cases for equivalence relation NDFD (non-divergent failures divergences).     

A constructive approach to solving 3-D geometric constraint systems using dependence analysis

Solving geometric constraint systems in 3-D is much more complicated than that in 2-D because the number of variables is larger and some of the results valid in 2-D cannot be extended for 3-D. In this paper, we propose a new DOF-based graph constructive method to geometric constraint systems solving that can efficiently handle well-, over- and under-constrained systems based on the dependence analysis. The basic idea is that the solutions of some geometric elements depend on some others because of the constraints between them. If some geometric elements depend on each other, they must be solved together. In our approach, we first identify all structurally redundant constraints, then we add some constraints to well constrain the system. And we prove that the order of a constraint system after processing under-constrained cases is not more than that of the original system multiplied by 5. After that, we apply a recursive searching process to identify all the clusters, which is shown to be capable of getting the minimum order-reduction result of a well-constrained system. We also briefly describe the constraint evaluation phase and show the implementation results of our method.     

Compact Data Structures and State-Space Reduction for Model-Checking Real-Time Systems

During the past few years, a number of verification tools have been developed for real-time systems in the framework of timed automata. One of the major problems in applying these tools to industrial-sized systems is the huge memory-usage for the exploration of the state-space of a network (or product) of timed automata, as the model-checkers must keep information about not only the control structure of the automata but also the clock values specified by clock constraints. In this paper, we present a compact data structure for representing clock constraints. The data structure is based on an O(n ³) algorithm which, given a constraint system over real-valued variables consisting of bounds on differences, constructs an equivalent system with a minimal number of constraints. In addition, we have developed an on-the-fly reduction technique to minimize the space-usage. Based on static analysis of the control structure of a network of timed automata, we are able to compute a set of symbolic states that cover all the dynamic loops of the network in an on-the-fly searching algorithm, and thus ensure termination in reachability analysis. The two techniques and their combination have been implemented in the tool UPPAAL. Our experimental results demonstrate that the techniques result in truly significant space-reductions: for six examples from the literature, the space saving is between 75% and 94%, and in (nearly) all examples time-performance is improved. Noteworthy is also the observation that the two techniques are completely orthogonal.     

A novel formulation for determining joint constraint loads during optimal dynamic motion of redundant manipulators in DH representation

The kinematic representations of general open-loop chains in many robotic applications are based on the Denavit–Hartenberg (DH) notation. However, when the DH representation is used for kinematic modeling, the relative joint constraints cannot be described explicitly using the common formulation methods. In this paper, we propose a new formulation of solving a system of differential-algebraic equations (DAEs) where the method of Lagrange multipliers is incorporated into the optimization problem for optimal motion planning of redundant manipulators. In particular, a set of fictitious joints is modeled to solve for the joint constraint forces and moments, as well as the optimal dynamic motion and the required actuator torques of redundant manipulators described in DH representation. The proposed method is formulated within the framework of our earlier study on the generation of load-effective optimal dynamic motions of redundant manipulators that guarantee successful execution of given tasks in which the Lagrangian dynamics for general external loads are incorporated. Some example tasks of a simple planar manipulator and a high-degree-of-freedom digital human model are illustrated, and the results show accurate calculation of joint constraint loads without altering the original planned motion. The proposed optimization formulation satisfies the equivalent DAEs.     

Symbolic execution of floating‐point computations

Symbolic execution is a classical program testing technique which evaluates a selected control flow path with symbolic input data. A constraint solver can be used to enforce the satisfiability of the extracted path conditions as well as to derive test data. Whenever path conditions contain floating‐point computations, a common strategy consists of using a constraint solver over the rationals or the reals. Unfortunately, even in a fully IEEE‐754‐compliant environment, this leads not only to approximations but also can compromise correctness: a path can be labelled as infeasible although there exists floating‐point input data that satisfy it. In this paper, the peculiarities of symbolic execution of programs with floating‐point numbers are addressed. Issues in the symbolic execution of this kind of program are carefully examined and a constraint solver is described that supports constraints over floating‐point numbers. Preliminary experimental results demonstrate the value of the approach proposed. Copyright © 2005 John Wiley & Sons, Ltd.     

Model Checking with Strong Fairness

In this paper we present a coherent framework for symbolic model checking of linear-time temporal logic (ltl) properties over finite state reactive systems, taking full fairness constraints into consideration. We use the computational model of a fair discrete system (fds) which takes into account both justice (weak fairness) and compassion (strong fairness). The approach presented here reduces the model-checking problem into the question of whether a given fds is feasible (i.e. has at least one computation). The contribution of the paper is twofold: On the methodological level, it presents a direct self-contained exposition of full ltl symbolic model checking without resorting to reductions to either μ-calculus or ctl. On the technical level, it extends previous methods by dealing with compassion at the algorithmic level instead of either adding it to the specification, or transforming compassion to justice. Finally, we extend ctl^∗ with past operators, and show that the basic symbolic feasibility algorithm presented here, can be used to model check an arbitrary ctl^∗ formula over an fds with full fairness constraints. This research was supported in part by an infra-structure grant from the Israeli Ministry of Science and Art, a grant from the U.S.-Israel Binational Science Foundation, and a gift from Intel.     

Sensitivity limitations in nonlinear feedback control

In this paper we define nonlinear sensitivity and complementary sensitivity operators of a feedback control loop and show that they satisfy a complemntarity constraint. We then consider the case of general nonlinear open-loop operators that give rise to nonlinear sensitivities that are Lipschitz operators on some Banach space. Under these conditions, we obtain lower bounds on the Lipschitz constants of both operators for open-loop nonminimum phase and unstable nonlinear systems. These results parallel those known in linear control theory on the H_∞ norms of S and T. We finally point to the relevance of the defined nonlinear sensitivities in robustness issues.     

A Reinforcement Learning Approach to Interval Constraint Propagation

When solving systems of nonlinear equations with interval constraint methods, it has often been observed that many calls to contracting operators do not participate actively to the reduction of the search space. Attempts to statically select a subset of efficient contracting operators fail to offer reliable performance speed-ups. By embedding the recency-weighted average Reinforcement Learning method into a constraint propagation algorithm to dynamically learn the best operators, we show that it is possible to obtain robust algorithms with reliable performances on a range of sparse problems. Using a simple heuristic to compute initial weights, we also achieve significant performance speed-ups for dense problems.     

Towards a Hybrid Dynamic Logic for Hybrid Dynamic Systems

We introduce a hybrid variant of a dynamic logic with continuous state transitions along differential equations, and we present a sequent calculus for this extended hybrid dynamic logic. With the addition of satisfaction operators, this hybrid logic provides improved system introspection by referring to properties of states during system evolution. In addition to this, our calculus introduces state-based reasoning as a paradigm for delaying expansion of transitions using nominals as symbolic state labels. With these extensions, our hybrid dynamic logic advances the capabilities for compositional reasoning about (semialgebraic) hybrid dynamic systems. Moreover, the constructive reasoning support for goal-oriented analytic verification of hybrid dynamic systems carries over from the base calculus to our extended calculus.     

Multibody dynamics with redundant constraints and singular mass matrix: existence, uniqueness, and determination of solutions for accelerations and constraint forces

This paper addresses some important issues for multibody dynamics; issues that are basic and really not too difficult to solve, but rarely considered in the literature. The aim of this paper is to contribute to the resolution and clarification of these topics in multibody dynamics. There are many formulations for determining the equations of motion in constrained multibody systems. This paper will focus on three of the most important methods: the Lagrange equations of the first kind, the null space method and the Maggi equations. In all cases we consider singular inertia matrices and redundant constraint equations. We assume that the inertia matrix is positive-semidefinite (symmetric) and that the constraint equations may be redundant but always consistent. It is demonstrated that the aforementioned dynamic formulations lead to the same three mathematical conditions of existence and uniqueness of solutions, conditions that have at the same time a clear physical meaning. We conclude that the mathematical problem always has a solution if the physical problem is well conditioned. This paper also addresses the problem of determining the constraint forces in the case of redundant constraints. This problem is examined from a broad perspective. We will present several examples and a simple method to find practical solutions in cases where the forces of constraint are undetermined. The method is based on the weighted minimum norm condition. A physical interpretation of this minimum norm condition is provided in detail for all examples. In some cases a comparison with the results obtained by considering flexibility is included.