On The Semantics And Expressiveness Of Ambient Calculi

Ambient Calculus is one of the most concerned process calculi studied in the field ofconcurrency theory due to its abstraction ability and importance in both theory and appli-cation. It has shown efficiency in modeling and analyzing mobile computation. Over theyears, many new variants of the ambient calculus have been proposed for practical or theo-retical reasons. Some important open problems have also been raised in the studies of thesevariants. Some of them have remained open for quite a long time. In the past few years,researches have showed interest in the relationships among different ambient calculi. Somehave started to study the relationship between the ambient calculi and some other processcalculi. However, as far as we know, the research carried out so far have not been done inan uniform way. In this thesis, we contribute to the big picture of ambient calculi in thefollowing way.1. We propose a new variant of the ambient calculus, i.e., the Half Parameterized SafeAmbients, features in the parameterless co-actions. The co-abilities can be inheritedby the outer ambients, which is different from the safe ambients calculus. We study thesemantic system and the labeled bisimulation relation of the half parameterized safeambient. We clarify the relationship between the labeled bisimulation and the reduc-tion barbed congruence. We then apply the techniques used in the half parameterizedsafe ambients to the study of the safe ambients.2. We take a look at two problems concerning the expressiveness of ambient calculi. Oneis about the absolute expressiveness. We study the process termination problem ofsome fragments of the Fair Ambients. The other is about the relative expressiveness.We redefine the criteria of the expressiveness comparison, and then prove some neg-ative results by making use of these criteria. Additionally, we give some encodingsbetween different variants of ambient calculi. In particular, we give two encodingsfromπcalculus to the safe ambients.3. We propose another new variant of ambient calculus, the Anonymous Ambients, whichis an extension of the Fair Ambient. Its special feature is a partial order over the ac-tion sets. Anonymous Ambient has interesting labeled transition systems and bisim- ulations. The algebraic property of the Anonymous Ambients is shown to be quiteelegant. An explanation of the mobile ambients without open operator is given.In summary, we focus in this thesis on two important problems in the ambient calculi—the semantic problem and the expressiveness problem. We make more extensive examinationof the previous work. Most of the work reported in this paper can be extended to offer insightinto the field. The research on the classic problems and the proposal of new models can gobeyond the area of ambient calculi.