Timed Concurrent Constraint Programming for Analysing Biological Systems

In this paper we present our first approach to model and verify biological systems using ntcc, a concurrent constraint process calculus. We argue that the partial information constructs in ntcc can provide a suitable language for such systems. We also illustrate how ntcc may provide a unified framework for the analysis of biological systems, as they can be described, simulated and verified using the elements provided by the calculus.     

Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control

Research on qualitative spatial reasoning has produced a variety of calculi for reasoning about orientation or direction relations. Such qualitative abstractions are very helpful for agent control and communication between robots and humans. Conceptual neighborhood has been introduced as a means of describing possible changes of spatial relations which e.g. allows action planning at a high level of abstraction. We discuss how the concrete neighborhood structure depends on application-specific parameters and derive corresponding neighborhood structures for the calculus. We demonstrate that conceptual neighborhoods allow resolution of conflicting information by model-based relaxation of spatial constraints. In addition, we address the problem of automatically deriving neighborhood structures and show how this can be achieved if the relations of a calculus can be modeled in another calculus for which the neighborhood structure is known.     

A core calculus for correlation in orchestration languages

We introduce a formal framework for studying the mechanism of correlation in orchestration languages for Web Services. A core calculus based on typical process algebraic constructs is developed, enhanced with two mechanisms: (i) a management of scopes keeping track of variables, properties, and their assignment to values, and (ii) a construct to spawn service instances handling (cor-)related operations and guaranteeing consistent routing of messages. By abstracting away from low-level details of orchestration languages, this model can be used as a foundation for the correlation mechanism, paving the way towards the analysis of properties and the design of extensions and improvements. As an example application, we show how the calculus introduced can be extended with few imperative and control-flow constructs reaching the expressiveness of a significant fragment of BPEL orchestration language.     

Privacy via Subsumption

We describe an object calculus allowing object extension and structural subtyping. Each object has a “dictionary” to mediate the connection between names and components. This extra indirection yields the first object calculus combining both object extension and full width subtyping in a type-safe manner. If class inheritance is modeled with object extension, private fields and methods can be achieved directly by scoping restrictions: private fields or methods are those hidden by subsumption. We prove that the type system is sound, discuss a variant allowing covariant self types, and give some examples of the expressiveness of the calculus.     

Reasoning algebraically about loops

We show how to formalise different kinds of loop constructs within the refinement calculus, and how to use this formalisation to derive general transformation rules for loop constructs. The emphasis is on using algebraic methods for reasoning about equivalence and refinement of loop constructs, rather than operational ways of reasoning about loops in terms of their execution sequences. We apply the algebraic reasoning techniques to derive a collection of transformation rules for action systems and for guarded loops. These include transformation rules that have been found important in practical program derivations: data refinement and atomicity refinement of action systems; and merging, reordering, and data refinement of loops with stuttering transitions. Received: 11 February 1998 / 18 March 1999     

Leader Election in Rings of Ambient Processes

Palamidessi has shown that the π-calculus with mixed choice is powerful enough to solve the leader election problem on a symmetric ring of processes. We show that this is also possible in the calculus of Mobile Ambients (MA), without using communication or restriction. Following Palamidessi's methods, we deduce that there is no encoding satisfying certain conditions from MA into CCS. We also show that the calculus of Boxed Ambients is more expressive than its communication-free fragment.     

Splitting Mobility and Communication in Boxed Ambients

Stemming from our previous work on BACI, a boxed ambient calculus with communication in- terfaces, we define a new calculus that further enhances communication mechanisms and mobility control by introducing multiple communication ports, access control lists, and port hiding.The development of the calculus is mainly focused on three objectives: separation of concerns between mobility and communication, fine-grained controls, and locality. Communication primi- tives use ports to establish communication channels between ambients, while ambient names are only used for mobility. In order to achieve a better control over mobility, the calculus includes co-capabilities à la Safe Ambients, but with the addition of access control lists. These lists contain the names of the ambients that are allowed to enter or exit the ambient with that co-capability.The resulting calculus not only provides more flexibility and expressiveness than Boxed Ambients, but also enables simpler implementations using more powerful constructs for communication and mobility. We establish the basic meta-theory of the calculus by providing rules for type safety and showing that typing is preserved during execution.     

Mechanising first-order temporal resolution

First-order temporal logic is a concise and powerful notation, with many potential applications in both Computer Science and Artificial Intelligence. While the full logic is highly complex, recent work on monodic first-order temporal logics has identified important enumerable and even decidable fragments. Although a complete and correct resolution-style calculus has already been suggested for this specific fragment, this calculus involves constructions too complex to be of practical value. In this paper, we develop a machine-oriented clausal resolution method which features radically simplified proof search. We first define a normal form for monodic formulae and then introduce a novel resolution calculus that can be applied to formulae in this normal form. By careful encoding, parts of the calculus can be implemented using classical first-order resolution and can, thus, be efficiently implemented. We prove correctness and completeness results for the calculus and illustrate it on a comprehensive example. An implementation of the method is briefly discussed.     

The Calculus of Context-aware Ambients

We present the Calculus of Context-aware Ambients (CCA in short) for the modelling and verification of mobile systems that are context-aware. This process calculus is built upon the calculus of mobile ambients and introduces new constructs to enable ambients and processes to be aware of the environment in which they are being executed. This results in a powerful calculus where both mobility and context-awareness are first-class citizens. We present the syntax and a formal semantics of the calculus. We propose a new theory of equivalence of processes which allows the identification of systems that have the same context-aware behaviours. We prove that CCA encodes the π-calculus which is known to be a universal model of computation. Finally, we illustrate the pragmatics of the calculus through many examples and a real-world case study of a context-aware hospital bed.     

ACE: An Associative Calculus Data Structure

The associative calculus is a methodology for problem solving using a natural-language interface. Associative calculus environment (ACE) is a language designed to eliminate ambiguities and misunderstandings that can occur when using English. ACE uses tables and charts as the basic data structure and is based on associative computing which uses content-addressable memory and responders. Parallelism is inherent in the ACE data structure and the expression syntax used for processing the referenced data. Thus, the programmer need not explicitly think about parallel constructs.     

An Intuitive Modelling Interface for Systems Biology

We introduce a natural language interface for building stochastic \pi calculus models of biological systems. In this language, complex constructs describing biochemical events are built from basic primitives of association, dissociation and transformation. This language thus allows us to model biochemical systems modularly by describing their dynamics in a narrative-style language, while making amendments, refinements and extensions on the models easy. We give a formal semantics for this language and a translation algorithm into stochastic \pi calculus that delivers this semantics. We demonstrate the language on a model of Fcr receptor phosphorylation during phagocytosis. We provide a tool implementation of the translation into a stochastic \pi calculus language, Microsoft Research''s SPiM, which can be used for simulation and analysis.     

Extending interaction overview diagrams with activity diagram constructs

UML2.0 introduced interaction overview diagrams (IODs) as a way of specifying relationships between UML interactions. IODs are a variant of activity diagrams that show control flow between a set of interactions. The nodes in an IOD are either inline interactions or references to an interaction. A number of recent papers have defined a formal semantics for IODs. These are restricted, however, to interactions that can be specified using basic sequence diagrams. This excludes the many rich modeling constructs available in activity diagrams such as interruptible regions, activity groups, concurrent node executions, and flow final nodes. It is non-trivial to allow such constructs in IODs because their meaning has to be interpreted in the context of interaction sequences rather than activities. In this paper, we consider how some of these activity diagram constructs can be used practically in IODs. We motivate the integration of these constructs into IODs using a NASA air traffic control subsystem and define a formal semantics for these constructs that builds on an existing semantics definition for IODs.     

A comprehensive comparison between generalized incidence calculus and the Dempster-Shafer theory of evidence

Dealing with uncertainty problems in intelligent systems has attracted a lot of attention in the AI community. Quite a few techniques have been proposed. Among them, the Dempster-Shafer theory of evidence (DS theory) has been widely appreciated. In DS theory, Dempster's combination rule plays a major role. However, it has been pointed out that the application domains of the rule are rather limited and the application of the theory sometimes gives unexpected results. We have previously explored the problem with Dempster's combination rule and proposed an alternative combination mechanism in generalized incidence calculus. In this paper we give a comprehensive comparison between generalized incidence calculus and the Dempster-Shafer theory of evidence. We first prove that these two theories have the same ability in representing evidence and combining DS-independent evidence. We then show that the new approach can deal with some dependent situations while Dempster's combination rule cannot. Various examples in the paper show the ways of using generalized incidence calculus in expert systems.     

A Calculus for Reconfiguration: (Extended abstract)

We present a simple calculus, called R-calculus (for “reconfiguration”), intended to provide a kernel model for a computational paradigm in which standard execution (that is, execution of a single computation described by a fragment of code) can be interleaved with operations at the meta-level which can manipulate in various ways the context in which this computation takes place. Formally, this is achieved by introducing as basic terms of the calculus configurations, which are, roughly speaking, pairs consisting of an (open, mutually recursive) collection of named components and a term representing a program running in the context of these components. The R-calculus has been originally developed as a formal model for programming-in-the large, where computations correspond to applications running in some context of software components, and operations at the meta-level correspond to the possibility of dynamically loading, updating or in general manipulat- ing these software components without stopping the application. However, the calculus can also encode programming-in-the-small issues, because configurations combine the features of lambda- abstractions (first-class functions), records, environments with mutually recursive definitions, and modules. We state confluence of the calculus and define a call-by-need strategy which leads to a generalization, including reconfiguration features, of call-by-need lambda-calculi.     

Types for the Ambient Calculus

The ambient calculus is a concurrent calculus where the unifying notion of ambient is used to model many different constructs for distributed and mobile computation. We study a type system that describes several properties of ambient behavior. The type system allows ambients to be partitioned in disjoint sets (groups), according to the intended design of a system, in order to specify both the communication and the mobility behavior of ambients.     

Classical Logic with Partial Functions

We introduce a semantics for classical logic with partial functions, in which ill-typed formulas are guaranteed to have no truth value, so that they cannot be used in any form of reasoning. The semantics makes it possible to mix reasoning about types and preconditions with reasoning about other properties. This makes it possible to deal with partial functions with preconditions of unlimited complexity. We show that, in spite of its increased complexity, the semantics is still a natural generalization of first-order logic with simple types. If one does not use the increased expressivity, the type system is not stronger than classical logic with simple types. We will define two sequent calculi for our semantics, and prove that they are sound and complete. The first calculus follows the semantics closely, and hence its completeness proof is fairly straightforward. The second calculus is further away from the semantics, but more suitable for practical use because it has better proof theoretic properties. Its completeness can be shown by proving that proofs from the first calculus can be translated.     

Lower bounds for the polynomial calculus

We show that polynomial calculus proofs (sometimes also called Groebner proofs) of the pigeonhole principle must have degree at least over any field. This is the first non-trivial lower bound on the degree of polynomial calculus proofs obtained without using unproved complexity assumptions. We also show that for some modifications of , expressible by polynomials of at most logarithmic degree, our bound can be improved to linear in the number of variables. Finally, we show that for any Boolean function in n variables, every polynomial calculus proof of the statement “ cannot be computed by any circuit of size t,” must have degree . Loosely speaking, this means that low degree polynomial calculus proofs do not prove . Received: January 15, 1997.