A General Name Binding Mechanism

  • Michele Boreale
  • Maria Grazia Buscemi
  • Ugo Montanari
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3705)


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.


Operational Semantic Expressive Power Parallel Composition Binding Mechanism Label Transition System 
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.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    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)CrossRefGoogle Scholar
  2. 2.
    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)CrossRefGoogle Scholar
  3. 3.
    Meredith, L.G., Bjorg, S., Richter, D.: Highwire Language Specification Version 1.0. (Unpublished manuscript)Google Scholar
  4. 4.
    Microsoft Corp. Biztalk Server,
  5. 5.
    Milner, R.: The Polyadic pi-Calculus: a Tutorial. Technical Report, Computer Science Dept., University of Edinburgh (1991)Google Scholar
  6. 6.
    Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes (parts I and II). Information and Computation 100(1), 1–77 (1992)CrossRefzbMATHMathSciNetGoogle Scholar
  7. 7.
    Nestmann, U., Pierce, B.C.: Decoding choice encodings. Information and Computation 163(1), 1–59 (2000)CrossRefzbMATHMathSciNetGoogle Scholar
  8. 8.
    Palamidessi, C.: Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus. In: Conf. Rec. of POPL 1997 (1997)Google Scholar
  9. 9.
    Palamidessi, C.: Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus. Mathematical Structures in Computer Science 13(5), 685–719 (2003)CrossRefMathSciNetGoogle Scholar
  10. 10.
    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)Google Scholar
  11. 11.
    Pistore, M., Sangiorgi, D.: A Partition Refinement Algorithm for the Pi-Calculus. Information and Computation 164(2), 264–321 (2001)CrossRefzbMATHMathSciNetGoogle Scholar
  12. 12.
    Sangiorgi, D.: Expressing Mobility in Process Algebras: First-Order and Higher-Order Paradigms. PhD thesis, Department of Computer Science, University of Edinburgh (1992)Google Scholar
  13. 13.
    Sangiorgi, D.: A Theory of Bisimulation for the pi-Calculus. Acta Informatica 33(1), 69–97 (1996)CrossRefMathSciNetGoogle Scholar
  14. 14.
    Victor, B.: The Fusion Calculus: Expressiveness and Symmetry in Mobile Processes. PhD thesis, Department of Computer Systems, Uppsala University (1998)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Michele Boreale
    • 1
  • Maria Grazia Buscemi
    • 2
  • Ugo Montanari
    • 2
  1. 1.Dipartimento di Sistemi e InformaticaUniversità di FirenzeItaly
  2. 2.Dipartimento di InformaticaUniversità di PisaItaly

Personalised recommendations