A Structured Way to Use Channels for Communication in X-Machine Systems

This paper presents a new model for passing messages in communicating stream X-machine systems (CSXMS). The components are stream X-machines with ε-transitions, acting simultaneously. The states are partitioned into processing and communicating states. Passing messages between the X-machines involves only communicating states. A communication matrix is used as a common memory. It is shown that a structured way of using channels, namely via select constructs with guarded alternatives and terminate clause, may be implemented. An automatic scheme for writing concurrent programs in an Ada-like style, starting from a CSXMS, is proposed. Received December 1999 / Accepted in revised form January 2001     

Process expressions and Hoare's logic: Showing an irreconcilability of context-free recursion with Scott's induction rule

In this paper processes specifiable over a non-uniform language are considered. The language contains constants for a set of atomic actions and constructs for alternative and sequential composition. Furthermore it provides a mechanism for specifying processes recursively (including nested recursion). We consider processes as having a state: atomic actions are to be specified in terms of observable behaviour (relative to initial states) and state transformations. Any process having some initial state can be associated with a transition system representing all possible courses of execution. This leads to an operational semantics in the style of Plotkin. The partial correctness assertion {α} p{β} expresses that for any transition system associated with the process p and having some initial state satisfying α, its final states representing successful execution satisfy β. A logic in the style of Hoare, containing a proof system for deriving partial correctness assertions, is presented. This proof system is sound and relatively complete, so any partial correctness assertion can be evaluated by investigating its derivability. Included is a short discussion about the extension of the process language with “guarded recursion”. It appears that such an extension violates the completeness of the Hoare logic. This reveals a remarkable property of Scott's induction rule in the context of non-determinism: only regular recursion allows a completeness result.     

Specification of communicating processes: temporal logic versus refusals-based refinement

In this paper we consider the relationship between refinement-oriented specification and specifications using a temporal logic. We investigate the extent to which one can check whether a program in a process algebra, such as Communicating Sequential Processes (CSP), satisfies a temporal logic specification using a refinement-based model checker, such as FDR. We consider what atomic formulae are appropriate in a temporal logic for specifying communicating processes, in particular where one wants to talk about the availability of events. We then show that, perhaps surprisingly, the standard stable failures model is not adequate for capturing specifications in such a logic: instead the refusal traces model must be used. We formalise the logic by giving it a semantics in this model. We show that the temporal operators eventually and until, and negation, cannot, in general, be tested for via simple refinement checks. For the remaining fragment of the logic, we present a translation into simple refinement checks. Finally, we show that refusal traces equivalence is characterised by a slightly augmented version of that fragment. M. J. Butler     

A Dynamic Logic of Agency II: Deterministic $${\mathcal{DLA}}$$ , Coalition Logic,and Game Theory

We continue the work initiated in Herzig and Lorini (J Logic Lang Inform, in press) whose aim is to provide a minimalistic logical framework combining the expressiveness of dynamic logic in which actions are first-class citizens in the object language, with the expressiveness of logics of agency such as STIT and logics of group capabilities such as CL and ATL. We present a logic called DDLA{\mathcal{DDLA}} (Deterministic Dynamic logic of Agency) which supports reasoning about actions and joint actions of agents and coalitions, and agentive and coalitional capabilities. In DDLA{\mathcal{DDLA}} it is supposed that, once all agents have selected a joint action, the effect of this joint action is deterministic. In order to assess DDLA{\mathcal{DDLA}} we prove that it embeds Coalition Logic. We then extend DDLA{\mathcal{DDLA}} with modal operators for agents’ preferences, and show that the resulting logic is sufficiently expressive to capture the game-theoretic concepts of best response and Nash equilibrium.     

A behavioral approach to the control of discrete linear repetitive processes

This paper formulates the theory of linear discrete time repetitive processes in the setting of behavioral systems theory. A behavioral, latent variable model for repetitive processes is developed and for the physically defined inputs and outputs as manifest variables, a kernel representation of their behavior is determined. Conditions for external stability and controllability of the behavior are then obtained. A sufficient condition for stabilizability is also developed for the behavior and it is shown under a mild restriction that, whenever the repetitive system is stabilizable, a regular constant output feedback stabilizing controller exists. Next, a notion of eigenvalues is defined for the repetitive process under an action of a closed-loop controller. It is then shown how under controllability of the original repetitive process, an arbitrary assignment of eigenvalues for the closed-loop response can be achieved by a constant gain output feedback controller under the above restriction. These results on the existence of constant gain output feedback controllers are among the most striking properties enjoyed by repetitive systems, discovered in this paper. Results of this paper utilize the behavioral model of the repetitive process which is an analogue of the 1D equivalent model of the dynamics studied in earlier work on these processes.     

Process algebra with guards: Combining Hoare logic with process algebra

We extend process algebra with guards, comparable to the guards in guarded commands or conditions in common programming constructs such as if — then — else — fi and while — do — od.The extended language is provided with an operational semantics based on transitions between pairs of a process and a (data-)state. The data-states are given by a data environment that also defines in which data-states guards hold and how atomic actions (non-deterministically) transform these states. The operational semantics is studied modulo strong bisimulation equivalence. For basic process algebra (without operators for parallelism) we present a small axiom system that is complete with respect to a general class of data environments. Given a particular data environmentL we add three axioms to this system, which is then again complete, provided weakest preconditions are expressible andL is sufficiently deterministic.Then we study process algebra with parallelism and guards. A two phase-calculus is provided that makes it possible to prove identities between parallel processes. Also this calculus is complete. In the last section we show that partial correctness formulas can easily be expressed in this setting. We use process algebra with guards to prove the soundness of a Hoare logic for linear processes by translating proofs in Hoare logic into proofs in process algebra.Supported by ESPRIT Basic Research Action no. 3006 (CONCUR) and by RACE project no. 1046 (SPECS).Supported by RACE project no. 1046 (SPECS).     

Modeling and testing object-oriented distributed systems with linear-time temporal logic

We present a framework for constructing formal models of object-oriented distributed systems and a property language to express behavioral constraints in such models. Most of the existing models have their origin in specific mathematical notations and/or concepts. In contrast, we have developed our model such that it accounts for a large set of phenomena associated with industrial implementations of object-oriented distributed systems. The model that we propose, while closer to industrial concerns and practice, still has the powerful features of formal approaches. It also offers the possibility to automatically check at service run-time that the final service implementation has not violated and is not violating properties expressed at the abstraction level of our model. In our model, which relies on event-based behavioral abstraction, we use linear-time temporal logic as the underlying formalism for the specification of properties. We introduce two novel operators which are especially useful for object-oriented systems and which provide a number of advantages over the well-known temporal logic operators. A recent decision of one of our industrial partners to adopt our proposal into one of their development platforms can be seen as a strong evidence of the relevance of our work and as a promising step towards a better understanding between the academic formal methods community and industry. Copyright © 2001 John Wiley & Sons, Ltd.     

Test suite minimization for testing in context

Testing a component embedded into a complex system, in which all other components are assumed fault‐free, is known as embedded testing. This paper proposes a method for minimizing a test suite to perform embedded testing. The minimized test suite maintains the fault coverage of the original test suite with respect to faults within the embedded component. The minimization uses the fact that the system is composed of a fault‐free context and a component under test, specified as communicating, possibly non‐deterministic finite state machines (FSMs). The method is illustrated using an example of telephone services on an intelligent network architecture. Other applications of the proposed approach for testing a system of communicating FSMs are also discussed. Copyright © 2003 John Wiley & Sons, Ltd.     

Automatic verification for a class of distributed systems

Summary. The paper presents a new analysis method for a class of concurrent systems which are formed of several interacting components with the same structure. The model for these systems is composed of a control process and a set of homogeneous user processes. The control and user processes are modeled by finite labeled state transition systems which interact by means of enabling functions and triggering mechanisms. Based on this structure, an analysis method is presented which allows system properties, derived by reachability analysis for a finite number of user processes, to be generalized to an arbitrary number of user processes. A procedure for the automatic verification of properties such as mutual exclusion and absence of deadlocks is presented and is then used to provide for the first time a fully automated verification of the Lamport's fast mutual exclusion algorithm. Received: October 1998/Accepted January 2000     

Reasoning about action and change

Reasoning about change is a central issue in research on human and robot planning. We study an approach to reasoning about action and change in a dynamic logic setting and provide a solution to problems which are related to the Frame problem. Unlike most work on the frame problem the logic described in this paper is monotonic. It (implicitly) allows for the occurrence of actions of multiple agents by introducing non-stationary notions of waiting and test. The need to state a large number of frame axioms is alleviated by introducing a concept of chronological preservation to dynamic logic. As a side effect, this concept permits the encoding of temporal properties in a natural way. We compare the relative merits of our approach and non-monotonic approaches as regards different aspects of the frame problem. Technically, we show that the resulting extended systems of propositional dynamic logic preserve (weak) completeness, finite model property and decidability.     

Guards,Bounds, and Generalized Semantics

Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) satisfiability on general assignment models for arbitrary first-order formulas. In particular, we give a new straightforward reduction from the former notion to the latter. We also show how a perspective shift to general assignment models provides a new look at the fixed-point extension LFP(FO) of first-order logic, making it decidable. Next, we relate guarded syntax to earlier quantifier restriction strategies for achieving effective axiomatizability in second-order logic – pointing at analogies with ‘persistent’ formulas, which are essentially in the Bounded Fragment of many-sorted first-order logic. Finally, we look at some further unexplored directions, including the systematic use of ‘quasi-models’ as a semantics by itself.     

Compositional message sequence charts

A message sequence chart (MSC) is a standard notation for describing the interaction between communicating objects. It is popular among the designers of communication protocols. MSCs enjoy both a visual and a textual representation. High-level MSCs (HMSCs) allow specifying infinite scenarios and different choices. Specifically, an HMSC consists of a graph, where each node is a finite MSC with matched send and receive events, and vice versa. In this paper we demonstrate a weakness of HMSCs, which disallows one to model certain interactions. We will show, by means of an example, that some simple finite state communication protocol cannot be represented using HMSCs. We then propose an extension to the MSC standard which allows HMSC nodes to include unmatched messages. The corresponding graph notation will be called HCMSC, which stands for high-level Compositional message sequence charts. With the extended framework, we provide an algorithm for automatically constructing an MSC representation for finite state asynchronous message passing protocols.     

Biological Transactions for Quantitative Models

In this work an extension of stochastic π-calculus with biological transactions is presented. This permits to model multi-reactant multi-product reactions as atomic actions when quantitative information are given. First, the syntax and the semantics are defined, then some transaction properties are discussed. Finally, some examples are described.     

Autonomous pedestrians

We address the challenging problem of emulating the rich complexity of real pedestrians in urban environments. Our artificial life approach integrates motor, perceptual, behavioral, and cognitive components within a comprehensive model of pedestrians as individuals. Featuring innovations in these components, as well as in their combination, our model yields results of unprecedented fidelity and complexity for fully autonomous multihuman simulation in a large urban environment. We represent the environment using hierarchical data structures, which efficiently support the perceptual queries that influence the behavioral responses of the autonomous pedestrians and sustain their ability to plan their actions on local and global scales.     

Completing open logic programs by constructive induction

We consider part of the problem of schema-biased inductive synthesis of recursive logic programs from incomplete specifications, such as clausal evidence (for instance, but not necessarily, ground positive and negative examples). After synthesizing the base clause and introducing recursive call(s) to the recursive clause, it remains to combine the overall result from the partial results obtained through recursion, so as to complete the recursive clause. Evidence for this combination relation can be abduced from the initially given evidence for the top-level relation. A program for this combination relation can be anything, from a single clause performing a unification (such as for lastElem) to multiple guarded clauses performing unifications (such as for filtering programs) to recursive programs (such as for naive reverse). Existing methods cannot induce guarded clause programs for this combination relation from the abduced evidence. Some existing methods cannot even detect that the combination program itself may have to be recursive and thus they then do not recursively invoke themselves the overall recursive program synthesizer. We introduce our Program Completion Method as a suitable extension and generalization of the existing methods. ©1999 John Wiley & Sons, Inc.     

Analogical proportions

Analogy-making is at the core of human and artificial intelligence and creativity with applications to such diverse tasks as proving mathematical theorems and building mathematical theories, common sense reasoning, learning, language acquisition, and story telling. This paper introduces from first principles an abstract algebraic framework of analogical proportions of the form ‘a is to b what c is to d’ in the general setting of universal algebra. This enables us to compare mathematical objects possibly across different domains in a uniform way which is crucial for AI-systems. It turns out that our notion of analogical proportions has appealing mathematical properties. As we construct our model from first principles using only elementary concepts of universal algebra, and since our model questions some basic properties of analogical proportions presupposed in the literature, to convince the reader of the plausibility of our model we show that it can be naturally embedded into first-order logic via model-theoretic types and prove from that perspective that analogical proportions are compatible with structure-preserving mappings. This provides conceptual evidence for its applicability. In a broader sense, this paper is a first step towards a theory of analogical reasoning and learning systems with potential applications to fundamental AI-problems like common sense reasoning and computational learning and creativity.

     

Exploring Temporal Structure of Trajectory Components for Action Recognition

Action recognition is one of the most important components for video analysis. In addition to objects and atomic actions, temporal relationships are important characteristics for many actions and are not fully exploited in many approaches. We model the temporal structures of midlevel actions (referred to as components) based on dense trajectory components, obtained by clustering individual trajectories. The trajectory components are a higher level and a more stable representation than raw individual trajectories. Based on the temporal ordering of trajectory components, we describe the temporal structure using Allen's temporal relationships in a discriminative manner and combine it with a generative model using bag of components. The main idea behind the model is to extract midlevel features from domain‐independent dense trajectories and classify the actions by exploring the temporal structure among these midlevel features based on a set of relationships. We evaluate the proposed approach on public data sets and compare it with a bag‐of‐words–based approach and state‐of‐the‐art application of the Markov logic network for action recognition. The results demonstrate that the proposed approach produces better recognition accuracy.     

Model checking for a probabilistic branching time logic with fairness

We consider concurrent probabilistic systems, based on probabilistic automata of Segala & Lynch [55], which allow non-deterministic choice between probability distributions. These systems can be decomposed into a collection of “computation trees” which arise by resolving the non-deterministic, but not probabilistic, choices. The presence of non-determinism means that certain liveness properties cannot be established unless fairness is assumed. We introduce a probabilistic branching time logic PBTL, based on the logic TPCTL of Hansson [30] and the logic PCTL of [55], resp. pCTL [14]. The formulas of the logic express properties such as “every request is eventually granted with probability at least p”. We give three interpretations for PBTL on concurrent probabilistic processes: the first is standard, while in the remaining two interpretations the branching time quantifiers are taken to range over a certain kind of fair computation trees. We then present a model checking algorithm for verifying whether a concurrent probabilistic process satisfies a PBTL formula assuming fairness constraints. We also propose adaptations of existing model checking algorithms for pCTL [4, 14] to obtain procedures for PBTL under fairness constraints. The techniques developed in this paper have applications in automatic verification of randomized distributed systems. Received: June 1997 / Accepted: May 1998