Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

When Ambients Cannot Be Opened

Iovka BonevaContact Information and Jean-Marc TalbotContact Information

(5)  Laboratoire d’Informatique Fondamentale de Lille, France
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.

Contact Information Iovka Boneva
Email: boneva@lifl.fr

Contact Information Jean-Marc Talbot
Email: talbot@lifl.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb19
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)