Extensionality and Intensionality of the Ambient Logics

Abstract

The ambient logic has been proposed for expressing properties of process mobility in the calculus of Mobile Ambients (MA), and as a basis for query languages on semistructured data. To understand the extensionality and the intensionality of the logic, the equivalence on MA processes induced by the logic (=L) iscompared with the standard MA behavioural equivalence and with structural congruence (an intensional equivalence, used as an auxiliary relation in thedefinition of satisfaction of the logic). The main contributions include a co-inductive characterisation of <=L as a form of labelled bisimilarity, and axiomatisations of <=L on the synchronous and asynchronous (finite) calculus. The study shows that, surprisingly, the logic allows us to observe the internal structure of the processes at a very finegrained detail, much in the same way as structural congruence does. A spin-off of the study is a better understanding of behavioural equivalence in Ambient-like calculi. For instance, behavioural equivalence is shown to be insensitive to stuttering phenomena originated by processes that may repeatedly enter and exit an ambient.