English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

The Decidability of Model Checking Mobile Ambients

MPS-Authors
/persons/resource/persons44232

Charatonik,  Witold
Programming Logics, MPI for Informatics, Max Planck Society;

/persons/resource/persons45585

Talbot,  Jean-Marc
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Charatonik, W., & Talbot, J.-M. (2001). The Decidability of Model Checking Mobile Ambients. In L. Fribourg (Ed.), Computer science logic (CSL-01): 15th International Workshop, CSL 2001, Annual Conference of the EACSL (pp. 339-354). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-324F-5
Abstract
The ambient calculus is a formalism for describing the mobility of both software and hardware. The ambient logic is a modal logic designed to specify properties of distributed and mobile computations programmed in the ambient calculus. In this paper we investigate the border between decidable and undecidable cases of model checking mobile ambients for some fragments of the ambient calculus and the ambient logic. Recently, Cardelli and Gordon presented a model-checking algorithm for a fragment of the calculus (without name restriction and without replication) against a fragment of the logic (without composition adjunct) and asked the question, whether this algorithm could be extended to include either replication in the calculus or composition adjunct in the logic. Here we answer this question negatively: it is not possible to extend the algorithm, because each of these extensions leads to undecidability of the problem. On the other hand, we extend the algorithm to the calculus with name restriction and logic with new constructs for reasoning about restricted names.