Computing Publications

Publications Home » On the computational strength of ...

On the computational strength of pure ambient calculi

Sergio Maffeis, Iain Phillips

Journal Article
Theoretical Computer Science
Volume 330
Issue 3
pp.501–551
2005
ISSN 0304-3975
DOI 10.1016/j.tcs.2004.10.007
Abstract

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
 

pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.