Abstract
We study fusion and binding mechanisms in name passing process calculi. To this purpose, we introduce the U-Calculus, a process calculus with no I/O polarities and a unique form of binding. The latter can be used both to control the scope of fusions and to handle new name generation. This is achieved by means of a simple form of typing: each bound name x is annotated with a set of exceptions, that is names that cannot be fused to x. The new calculus is proven to be more expressive than pi-calculus and Fusion calculus separately. In U-Calculus, the syntactic nesting of name binders has a semantic meaning, which cannot be overcome by the ordering of name extrusions at runtime. Thanks to this mixture of static and dynamic ordering of names, U-Calculus admits a form of labelled bisimulation which is a congruence. This property yields a substantial improvement with respect to previous proposals by the same authors aimed at unifying the above two languages. The additional expressiveness of U-Calculus is also explored by providing a uniform encoding of mixed guarded choice into the choice-free sub-calculus.
Research partially supported by IST FET Global projects PROFUNDIS IST-2001-33100 and MIKADO IST-2001-32222.
An erratum to this chapter can be found at http://dx.doi.org/10.1007/11580850_20 .
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Boreale, M., Buscemi, M., Montanari, U.: D-Fusion: a Distinctive Fusion Calculus. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 296–310. Springer, Heidelberg (2004)
Gardner, P., Laneve, C., Wischik, L.: The fusion machine (extended abstract). In: Brim, L., Jančar, P., Křetínský, M., Kucera, A. (eds.) CONCUR 2002. LNCS, vol. 2421, p. 418. Springer, Heidelberg (2002)
Meredith, L.G., Bjorg, S., Richter, D.: Highwire Language Specification Version 1.0. (Unpublished manuscript)
Microsoft Corp. Biztalk Server, http://www.microsoft.com/biztalk
Milner, R.: The Polyadic pi-Calculus: a Tutorial. Technical Report, Computer Science Dept., University of Edinburgh (1991)
Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes (parts I and II). Information and Computation 100(1), 1–77 (1992)
Nestmann, U., Pierce, B.C.: Decoding choice encodings. Information and Computation 163(1), 1–59 (2000)
Palamidessi, C.: Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus. In: Conf. Rec. of POPL 1997 (1997)
Palamidessi, C.: Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus. Mathematical Structures in Computer Science 13(5), 685–719 (2003)
Parrow, J., Victor, B.: The Fusion Calculus: Expressiveness and Symmetry in Mobile Processes. In: Proc. of LICS 1998. IEEE Computer Society Press, Los Alamitos (1998)
Pistore, M., Sangiorgi, D.: A Partition Refinement Algorithm for the Pi-Calculus. Information and Computation 164(2), 264–321 (2001)
Sangiorgi, D.: Expressing Mobility in Process Algebras: First-Order and Higher-Order Paradigms. PhD thesis, Department of Computer Science, University of Edinburgh (1992)
Sangiorgi, D.: A Theory of Bisimulation for the pi-Calculus. Acta Informatica 33(1), 69–97 (1996)
Victor, B.: The Fusion Calculus: Expressiveness and Symmetry in Mobile Processes. PhD thesis, Department of Computer Systems, Uppsala University (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boreale, M., Buscemi, M.G., Montanari, U. (2005). A General Name Binding Mechanism. In: De Nicola, R., Sangiorgi, D. (eds) Trustworthy Global Computing. TGC 2005. Lecture Notes in Computer Science, vol 3705. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11580850_5
Download citation
DOI: https://doi.org/10.1007/11580850_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30007-6
Online ISBN: 978-3-540-31483-7
eBook Packages: Computer ScienceComputer Science (R0)