Abstract Given the complexity of cyber-physical systems (CPS), such as swarms of drones, often deviations, from a planned mission or protocol, occur which may in some cases lead to harm and losses. To increase the robustness of such systems, it is necessary to detect when deviations happen and diagnose the cause(s) for a deviation. We build on our previous work on soft agents, a formal framework based on using rewriting logic for specifying and reasoning about distributed CPS, to develop methods for diagnosis of CPS at design time. We accomplish this by (1) extending the soft agents framework with Fault Models; (2) proposing a protocol specification language and the definition of protocol deviations; and (3) development of workflows/algorithms for detection and diagnosis of protocol deviations. Our approach is partially inspired by existing work using counterfactual reasoning for fault ascription. We demonstrate our machinery with a collection of experiments.

We present an actor language which is an extension of a simple functional language, and provide an operational semantics for this extension. Actor configurations represent open distributed systems, by which we mean that the specification of an actor system explicitly takes into account the interface with external components. We study the composability of such systems. We define and study various notions of testing equivalence on actor expressions and configurations. The model we develop provides fairness. An important result is that the three forms of equivalence, namely, convex, must, and may equivalences, collapse to two in the presence of fairness. We further develop methods for proving laws of equivalence and provide example proofs to illustrate our methodology.

This paper builds domain theoretic concepts upon an operational foundation. The basic operational theory consists of a single step reduction system from which an operational ordering and equivalence on programs are defined. The theory is then extended to include concepts from domain theory, including the notions of directed set, least upper bound, complete partial order, monotonicity, continuity, finite element, ω -algebraicity, full abstraction, and least fixed point properties. We conclude by using these concepts to construct a (strongly) fully abstract continuous model for our language. In addition we generalize a result of Milner and prove the uniqueness of such models.

In this paper we investigate the simple logical properties of contexts. We describe both the syntax and semantics of a general propositional language of context, and we give a Hilbert style proof system for this language. A propositional logic of context extends classical propositional logic in two ways. Firstly, a new modality, ist(κ,φ), is introduced. It is used to express that the sentence,φ, holds in the context, κ. Secondly, each context has its own vocabulary, i.e. a set of propositional atoms which are defined or meaningful in that context. The main results of this paper are the soundness and completeness of this Hilbert style proof system. We also provide soundness and completeness results (i.e., correspondence theory) for various extensions of the general system. Finally, we prove that our logic is decidable, and give a brief comparison of our semantics to Kripke semantics.

In this paper we introduce a variable typed logic of effects inspired by the variable type systems of Feferman for purely functional languages. VTLoE (Variable Typed Logic of Effects) is introduced in two stages. The first stage is the first-order theory of individuals built on assertions of equality (operational equivalence à la Plotkin), and contextual assertions. The second stage extends the logic to include classes and class membership. The logic we present provides an expressive language for defining and studying properties of programs including program equivalences, in a uniform framework. The logic combines the features and benefits of equational calculi as well as program and specification logics. In addition to the usual first-order formula constructions, we add contextual assertions. Contextual assertions generalize Hoare′s triples in that they can be nested, they can be used as assumptions, and their free variables can be quantified. They are similar in spirit to program modalities in dynamic logic. We use the logic to establish the validity of the Meyer Sieber examples in an operational setting. The theory allows for the construction of inductively defined sets and derivation of the corresponding induction principles. We hope that classes may serve as a starting point for studying semantic notions of type. Naive attempts to represent ML types as classes fail in the sense that ML inference rules are not valid.

Describes a method for extracting 3D events from a 3D volume of seismic data for the purposes of geophysical interpretation. An event is the recorded waveform caused by a seismic scatterer. It can be modeled as a hyperboloid with local perturbations. Extraction is difficult because of the local perturbations and, particularly, because events cross one another. The original data is in the form of 2D time sections which are vertical slices through the data volume. Once the event has been extracted, it is represented by fitting two types of surfaces. The first surface is a hyperboloid. The parameters that define the hyperboloid are used to determine geophysical parameters such as the position of the scatterer and the Earth's average propagation velocity. The second is a smooth approximating surface calculated using a regularising term. This surface is useful for visualising regions where the event pulls away from pure hyperbolic form.>

This paper describes a method for extracting 3D events from a 3D volume of seismic data for the purposes of geophysical interpretation. An event is the recoded waveform caused by a seismic scatterer. It can be modeled as hyperboloids with local perturbations. Extraction is difficult because of the local perturbations and, particularly, because events cross one another. The original data is in the form of 2D time sections which are vertical slices through the data volume. Constraints based on the physics of the seismic experiment are used to extract 2D event curves from the time sections and then combine them into 3D events. Two types of surfaces are fitted to the 3D event so that meaningful interpretations can be made.

eMail peter.tu*Q>eng.ox.ac.uk In this paper we introduce a three stage approach for extracting events from a seismic time section. The approach incorporates recent, techniques from computer vision such as deformable templates and multiple hypothesis tracking, and also takes advantage of constraints arising from the physics of seismic reflectors. First, a 2D local matched fdtering scheme is used to reduce the time section to a collection of event tokens suitable for tracking with a Kalman filter. Second, a multiple tracking system is used to analyse regions with crossing events. By using a dynamic model of event shape parameters, Kalman filters are able to track events that deviate from an ideal form. Finally, based on events found through Kalman filtering, flexible templates are used to exploit similarity between events. Due to the global nature of the flexible template search process, even events with sections of poor visibility can be identified. Based on this research, a semi-automatic system for extracting seismic events has been developed.

A.R. Meyer and K. Sieber (Proc. 15th ACM. Symp. on Principles of Programming Languages, 1988, p.191-208) gave a series of examples of programs that are operationally equivalent (according to the intended semantics of block-structured Algol-like programs) but are not given equivalent denotations in traditional denotational semantics. They propose various modifications to the denotational semantics that solve some of these discrepancies, but not all. The present authors approach the same problem, but from an operational rather than a denotational perspective. They present the first-order part of a new logic for reasoning about programs, and they use this logic to prove the equivalence of the Meyer-Sieber examples.>

In this paper we report progress in the development of methods for reasoning about the equivalence of objects with memory, and the use of these methods to describe sound operations on objects in terms of formal program transformations. We also formalize three different aspects of objects: their specification, their behavior, and their canonical representation. Formal connections among these aspects provide methods for optimization and reasoning about systems of objects. To illustrate these ideas we give a formal derivation of an optimized specialized window editor from generic specifications of its components. A new result in this paper enables one to make use of symbolic evaluation (with respect to a set of constraints) to establish the equivalence of objects. This form of evaluation is not only mechanizable, it is also generalizes the conditions under which partial evaluation usually takes place. 1 Overview In [19] a general challenge for partial evaluation technology was presented ...

Abstract Traditionally the view has been that direct expression of control and store mechanisms and clear mathematical semantics are incompatible requirements. This paper shows that adding objects with memory to the call-by-value lambda calculus results in a language with a rich equational theory, satisfying many of the usual laws. Combined with other recent work, this provides evidence that expressive, mathematically clean programming languages are indeed possible.

The authors present a formal system for deriving assertions about programs with side effects. The assertions considered are the following: (i) the expression e diverges (i.e. fails to reduce to a value); and (ii) e/sub 0/ and e/sub 1/ are strongly isomorphic (i.e. reduce to the same value and have the same effect on memory up to production of garbage). The e, e/sub j/ are expressions of a first-order scheme- or Lisp-like language with the data operations atom, eq, car, cdr, cons, setcar, setcdr, the control primitives let and if, and recursive definition of function symbols.>

In this paper we investigate the first order metatheory of the classical propositional logic. In the first section we prove that the first order metatheory of the classical propositional logic is undecidable. Thus as a mathematical object even the simplest of logics is, from a logical standpoint, quite complex. In fact it is of the same complexity as true first order number theory. This result answers negatively a question of J. F. A. K. van Benthem (see [van Benthem and Doets 1983]) as to whether the interpolation theorem in some sense completes the metatheory of the calculus. Let us begin by motivating the question that we answer. In [van Benthem and Doets 1983] it is claimed that a folklore prejudice has it that interpolation was the final elementary property of first order logic to be discovered. Even though other properties of the propositional calculus have been discovered since Craig's orginal paper [Craig 1957] (see for example [Reznikoff 1965]) there is a lot of evidence for the fundamental nature of the property. In abstract model theory for example one finds that very few logics have the interpolation property. There are two well-known open problems in this area. These are 1. Is there a logic satisfying the full compactness theorem as well as the interpolation theorem that is not equivalent to first order logic even for finite models? 2. Is there a logic stronger than L(Q), the logic with the quantifierthere exist uncountably many, that is countably compact and has the interpolation property?