When Ambients Cannot be Opened

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. The authors are grateful to S. Tison and Y. Roos for fruitful discussions and thank the anony mous ferees for valuable comments. This work is supported by an ATIP grant from CNRS.
Type de document :
Communication dans un congrès
Andrew D. Gordon. Proceedings of Sixth International Conference on Foundations of Software Science and Computation Structures, 2003, Warsaw, Poland. Springer, pp.169 -- 184, 2003, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536732
Contributeur : Iovka Boneva <>
Soumis le : mardi 16 novembre 2010 - 18:34:49
Dernière modification le : mardi 24 avril 2018 - 13:37:29
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:09:19

Fichier

BonevaTalbot-WhenAmbientsCanno...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536732, version 1

Collections

Citation

Iovka Boneva, Jean-Marc Talbot. When Ambients Cannot be Opened. Andrew D. Gordon. Proceedings of Sixth International Conference on Foundations of Software Science and Computation Structures, 2003, Warsaw, Poland. Springer, pp.169 -- 184, 2003, Lecture Notes in Computer Science. 〈inria-00536732〉

Partager

Métriques

Consultations de la notice

184

Téléchargements de fichiers

131