Skip to Main content Skip to Navigation
Journal articles

When Ambients Cannot be Opened

Iovka Boneva 1 Jean-Marc Talbot 1
1 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We investigate expressiveness of a fragment of the ambient calculus, a formalism for describing distributed and mobile computations. More precisely, we study expressiveness of the pure and public ambient calculus from which the capability open has been removed, in terms of the reachability problem of the reduction relation. Surprisingly, we show that even for this very restricted fragment, the reachability problem is not decidable. At a second step, for a slightly weaker reduction relation, we prove that reachability can be decided by reducing this problem to markings reachability for Petri nets. Finally, we show that the name-convergence problem as well as the model-checking problem turn out to be undecidable for both the original and the weaker reduction relation.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00536689
Contributor : Iovka Boneva Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2010 - 5:31:12 PM
Last modification on : Tuesday, March 23, 2021 - 3:48:47 PM

Links full text

Identifiers

Collections

Citation

Iovka Boneva, Jean-Marc Talbot. When Ambients Cannot be Opened. Theoretical Computer Science, Elsevier, 2005, 2 (333), pp.127-169. ⟨10.1016/j.tcs.2004.10.020⟩. ⟨inria-00536689⟩

Share

Metrics

Les métriques sont temporairement indisponibles