Computing Publications

Publications Home » On the Computational Strength of ...

On the Computational Strength of Pure Ambient Calculi

Sergio Maffeis, Iain Phillips

Conference or Workshop Paper
10th International Workshop on Expressiveness in Concurrency (EXPRESS'03), September 2, 2003, Marseille, France
Electronic Notes in Theoretical Computer Science
Volume 96
June, 2004
DOI 10.1016/j.entcs.2004.04.020

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.

BibTEX file for the publication built & maintained by Ashok Argent-Katwala.