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.     

Using ambients to control resources

Current software and hardware systems, being parallel and reconfigurable, raise new safety and reliability problems, and the resolution of these problems requires new methods. Numerous proposals aim at reducing the threat of bugs and preventing several kinds of attacks. In this paper, we develop an extension of the calculus of mobile ambients, named controlled ambients, that is suited for expressing such issues, specifically denial of service attacks. We present a type system for controlled ambients, which makes static resource control possible in our setting, and enhance it with a rich notion of resources .     

Ambient Petri Nets

Both the Ambient Calculus by L. Cardelli and the Elementary Object Systems by R. Valk model the behaviour of mobile systems. The Ambient Calculus is based on the concept of ambient, which is an environment with a given name that is delimited by a boundary, where some internal processes are executed. The main property of these ambients is that they can be moved to a new location thus modeling mobility. Elementary Object Systems are two-level net systems composed of a system net and one or more object nets, which can be seen as high-level token objects of the system net modeling the execution of mobile processes. This paper intends to contribute to the relationship between both frameworks by defining a multilevel extension of Elementary Object Systems, which will be used to provide a denotational semantics of a new process algebra called APBC (Ambient Petri Box Calculus). Such process algebra is an extension of the Petri Box Calculus that includes both ambients and their mobility capabilities, which conversely can be also interpreted as an extension of the Ambient Calculus with the main operations from the PBC.     

移动界程演算理论及应用研究综述

移动界程演算通过界程这一核心概念来表达有边界的计算场所,并提供界程移动,认证和授权等能力从最基础层次刻画移动计算的本质,成为了移动计算系统形式化理论和应用领域内的重要研究分支。对移动界程演算的理论及应用方面的研究和发展进行了概述,对移动界演算的扩展语义和代数性质的分析方法、移动界演算的空间逻辑和模型检测算法以及移动界程在计算系统建模方面应用现状进行了整理和分析,并对该领域未来进一步研究的方向进行了展望。     

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.     

On the Expressiveness of Pure Mobile Ambients

We consider the Pure Ambient Calculus, which is Cardelli and Gordon's Ambient Calculus (or more precisely its safe version by Levi and Sangiorgi) restricted to its mobility primitives, and we focus on its expressive power. Since it has no form of communication or substitution, we show how these notions can be simulated by mobility and modifications in the hierarchical structure of ambients. As an example, we give an encoding of the synchronous π-calculus into pure ambients and we state an operational correspondence result. In order to simplify the proof and give an intuitive understanding of the encoding, we design an intermediate language: the π-Calculus with Explicit Substitutions and Channels, which is a syntactic extension of the π-calculus with a specific operational semantics.     

On the Expressiveness of Pure Mobile Ambients

We consider the Pure Ambient Calculus, which is Cardelli and Gordon's Ambient Calculus (or more precisely its safe version by Levi and Sangiorgi) restricted to its mobility primitives, and we focus on its expressive power. Since it has no form of communication or substitution, we show how these notions can be simulated by mobility and modifications in the hierarchical structure of ambients. As an example, we give an encoding of the synchronous π-calculus into pure ambients and we state an operational correspondence result. In order to simplify the proof and give an intuitive understanding of the encoding, we design an intermediate language: the π-Calculus with Explicit Substitutions and Channels, which is a syntactic extension of the π-calculus with a specific operational semantics.     

Mutual mobile membranes with objects on surface

In this paper we study systems of mutual mobile membranes with objects on surface using pino/exo/phago rules. Their rules are applicable whenever there is a mutual agreement between membranes expressed by appropriate objects and co-objects on their surfaces. We investigate the computational power of these systems, and also relate them to brane calculi by encoding the PEP fragment of brane calculus into the systems of mutual mobile membranes with objects on surface.     

On the expressive power of movement and restriction in pure mobile ambients

Pure mobile ambients is a process calculus suitable to focus on issues related to mobility, abstracting away from aspects concerning process communication. However, it incorporates name restriction (i.e. the (νn) binder) and ambient movement (i.e. the in and out capabilities) that can be seen as characteristics adapted, or directly borrowed, from the tradition of communication-based process calculi. For this reason, we retain that it is worth to investigate whether or not these features can be removed from pure mobile ambients without losing expressive power.To this aim, we consider two variants of pure mobile ambients which differ in the way infinite processes can be defined; the former exploits process replication, while the latter is more general and permits recursive process definition. We analyse whether or not the elimination of ambient movement and/or name restriction reduces the expressive power of these two calculi, using the decidability of process termination as a yardstick. We prove that name restriction can be removed from both calculi without reducing the expressive power. On the other hand, the elimination of both ambient movement and name restriction strictly reduces the expressive power of both calculi. As far as the elimination of only ambient movement is concerned, we prove an interesting discrimination result: process termination is undecidable under recursive process definition, while it turns out to be decidable under process replication.     

Solving a weak NP-complete problem in polynomial time by using mutual mobile membrane systems

Mutual mobile membrane systems represent a variant of mobile membrane systems in which endocytosis and exocytosis work whenever the involved membranes ??agree?? on the movement by using mutual complement objects placed in membranes. We provide a semi-uniform polynomial solution for a weak NP-complete problem (namely partition problem) by means of mutual mobile membrane systems.     

On the power and size of extended gemmating P systems

In [3] P systems with gemmation of mobile membranes were examined. It was shown that (extended) systems with eight membranes are as powerful as the Turing machines. Moreover, it was proved that extended gemmating P systems with only pre-dynamical rules are still computationally complete: in this case nine membranes are needed to obtain this computational power. In this paper we improve the above results concerning the size bound of extended gemmating P systems, namely we prove that these systems with at most five membranes (with meta-priority relations and without communication rules) form a class of universal computing devices, while in the case of extended systems with only pre-dynamical rules six membranes are enough to determine any recursively enumerable language.     

移动灰箱演算中强干扰问题的进一步控制

为了消除移动灰箱演算中的强干扰问题,Levi等人提出了安全灰箱演算.然而,安全灰箱演算中引入的反动作却带来了新的安全隐患.为了消除上述安全隐患,提出了鲁棒灰箱演算.鲁棒灰箱演算在依靠反动作解决强干扰问题的同时,利用反动作的参数明确了该反动作的使用对象,有效地消除了安全灰箱演算中的不安全因素.对防火墙跨越的描述和对多元异步(-演算的翻译显示鲁棒灰箱演算依然具有较强的类似移动灰箱演算和安全灰箱演算的表达能力.同时还就鲁棒灰箱演算的类型问题作了初步的探讨,给出并证明了一套可以描述进程和能力的移动性和线程数两个属性的类型系统.研究结果初步表明,鲁棒灰箱演算可以成为移动计算形式化描述中的有力工具.     

Name-Passing in an Ambient-Like Calculus and Its Proof Using Spatial Logic

This paper studies a restricted version of the ambient calculus. We only allow single-threaded ambients migrating in a network of immobile ambients, exchanging payloads, and delivering them. With this restriction, we arrive at a calculus free from grave interferences. In previous works, this is only possible by sophisticated type systems.We focus on the expressiveness of the restricted calculus. We show that we can still repeat Zimmer's encoding of name-passing in our calculus. Moreover, we prove a stronger operational correspon- dence result using a novel spatial logic, which specifies spatial properties of processes invariant to process reductions.     

Stochastic Ambient Calculus

Mobile Ambients (MA) have acquired a fundamental role in modelling mobility in systems with mobile code and mobile devices, and in computation over administrative domains. We present the stochastic version of Mobile Ambients, called Stochastic Mobile Ambients (SMA), where we extend MA with time and probabilities. Inspired by previous models, PEPA and Sπ, we enhance the prefix of the capabilities with a rate and the ambient with a linear function that operates on the rates of processes executing inside it. The linear functions associated with ambients represent the delays that govern particular administrative domains. We derive performance measures from the labelled transition semantics as in standard models. We also define a strong Markov bisimulation in the style of reduction semantics known as barbed bisimulation. We argue that performance measures are of vital importance in designing any kind of distributed system, and that SMA can be useful in the design of the complicated mobile systems.     

Control Flow Analysis for BioAmbients

This paper presents a static analysis for investigating properties of biological systems specified in BioAmbients. We exploit the control flow analysis to decode the bindings of variables induced by communications and to build a relation of the ambients that can interact with each other. We eventually apply our analysis to an example of gene regulation by positive feedback taken from the literature.     

Predicate μ-Calculus for Mobile Ambients

Ambient logics have been proposed to describe properties for mobile agents which may evolve over time as well as space. This paper takes a predicate-based approach to extending an ambient logic with recursion, yielding a predicate μ-calculus in which fixpoint formulas are formed using predicate variables. An algorithm is developed for model checking finite-control mobile ambients against formulas of the logic, providing the first decidability result for model checking a spatial logic with recursion.     

Communication via Mobile Vesicles in Brane Calculi

P systems and Brane calculi are two (families of) computational models inspired by the structure and the functioning of living cells. Although they have different goals there is a recent growing of interests in results that bridge the two research areas.Here we consider an important kind of communication based on the natural budding of mobile membranes (e.g., Golgi apparatus) that is already defined for P systems and we show how to construct an analogous communication in the basic Phago/Exo/Pino Brane calculus.     

移动机器人避障行为酶数值膜控制器

为了兼顾膜控制器控制下的移动机器人行走速度和避障效果,提出了一种基于酶数值膜系统的自适应巡航速度避障控制方法.该方法采用酶数值膜系统结构,利用膜之间的信息交流,实现多个膜融合多个传感器的距离信息,根据融合距离信息自适应调节巡航速度,使移动机器人能够有效的避开障碍物,同时兼顾无障碍物时移动机器人行走速度.基于移动机器人Pioneer3-DX的仿真和实物实验表明：该方法设计的酶数值膜控制器可行且避障控制效果更优.     

On the computational strength of pure ambient calculi

Cardelli and Gordon's calculus of Mobile Ambients has attracted widespread interest as a model of mobile computation. The standard calculus is quite rich, with a variety of operators, together with capabilities for entering, leaving and dissolving ambients. The question arises of what is a minimal Turing-complete set of constructs. Previous work has established that Turing completeness can be achieved without using communication or restriction. We show that it can be achieved merely using movement capabilities (and not dissolution). We also show that certain smaller sets of constructs are either terminating or have decidable termination.