Orderly communication in the Ambient Calculus

摘要

The Ambient Calculus (henceforth, AC) was developed by Cardelli and Gordon as a formal framework to study issues of mobility and migrant code (In: Nivat M, editor. FoSSaCS '98, Lecture Notes in Computer Science, vol. 1378. Berlin: Springer, 1998. p. 140-55). We present a type system for AC that allows the type of exchanged data within the same ambient to vary over time. Our type system assigns what we call behaviors to processes; a denotational semantics of behaviors is proposed, here called trace semantics, underlying much of the remaining analysis. We state and prove a subject reduction property for our typed version of AC. Based on techniques borrowed from finite automata theory, type checking of fully type-annotated processes is shown to be decidable. We show that the typed version of AC originally proposed by Cardelli and Gordon (In: POPL'99, San Antonio, TX. New York: ACM Press, 1999. p. 79-92) can be naturally embedded into our typed version of AC.