×

Symmetries and dualities in name-passing process calculi. (English) Zbl 1323.68409

Calude, Cristian S. (ed.) et al., Computing with new resources. Essays dedicated to Jozef Gruska on the occasion of his 80th birthday. Cham: Springer (ISBN 978-3-319-13349-2/pbk; 978-3-319-13350-8/ebook). Lecture Notes in Computer Science 8808, 307-322 (2014).
Summary: We study symmetries and duality between input and output in the \(\pi \)-calculus. We show that in dualisable versions of \(\pi \), including \(\pi \) and fusions, duality breaks with the addition of ordinary input/output types. We illustrate two proposals of calculi that overcome these problems. One approach is based on a modification of fusion calculi in which the name equivalences produced by fusions are replaced by name preorders, and with a distinction between positive and negative occurrences of names. The resulting calculus allows us to import subtype systems, and related results, from the pi-calculus. The second approach consists in taking the minimal symmetrical conservative extension of \(\pi \) with input/output types.
For the entire collection see [Zbl 1318.68011].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boreale, M., Buscemi, M.G., Montanari, U.: A General Name Binding Mechanism. In: De Nicola, R., Sangiorgi, D. (eds.) TGC 2005. LNCS, vol. 3705, pp. 61–74. Springer, Heidelberg (2005) · Zbl 1151.68508 · doi:10.1007/11580850_5
[2] Fu, Y.: The \[ \chi \] -calculus. In: Proc. APDC, pp. 74–81. IEEE Computer Society Press (1997)
[3] Gardner, P., Wischik, L.: Explicit fusions. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, p. 373. Springer, Heidelberg (2000) · Zbl 0996.68523 · doi:10.1007/3-540-44612-5_33
[4] Hirschkoff, D., Madiot, J.-M., Sangiorgi, D.: Duality and i/o-types in the \[ \pi \] -calculus. In: Koutny, M., Ulidowski, I. (eds.) CONCUR 2012. LNCS, vol. 7454, pp. 302–316. Springer, Heidelberg (2012) · Zbl 1365.68343 · doi:10.1007/978-3-642-32940-1_22
[5] Hirschkoff, D., Madiot, J.M., Sangiorgi, D.: Name-Passing Calculi: From Fusions to Preorders and Types. long version of the paper presented at LICS’13, in preparation (2014) · Zbl 1366.68205
[6] Hirschkoff, D., Madiot, J.M., Xu, X.: A behavioural theory for a \[ \pi \] -calculus with preorders. submitted (2014) · Zbl 1434.68328
[7] Honda, K., Yoshida, N.: On reduction-based process semantics. Theor. Comp. Sci. 152(2), 437–486 (1995) · Zbl 0871.68122 · doi:10.1016/0304-3975(95)00074-7
[8] Laneve, C., Victor, B.: Solos in Concert. Mathematical Structures in Computer Science 13(5), 657–683 (2003) · doi:10.1017/S0960129503004055
[9] Milner, R.: Functions as processes. Mathematical Structures in Computer Science 2(2), 119–141 (1992) · Zbl 0773.03012 · doi:10.1017/S0960129500001407
[10] Parrow, J., Victor, B.: The fusion calculus: expressiveness and symmetry in mobile processes. In: Proc. of LICS, pp. 176–185. IEEE (1998) · doi:10.1109/LICS.1998.705654
[11] Parrow, J., Victor, B.: The update calculus (extended abstract). In: Johnson, M. (ed.) AMAST 1997. LNCS, vol. 1349, pp. 409–423. Springer, Heidelberg (1997) · doi:10.1007/BFb0000486
[12] Pierce, B.C., Sangiorgi, D.: Typing and subtyping for mobile processes. Mathematical Structures in Computer Science 6(5), 409–453 (1996) · Zbl 0861.68030
[13] Sangiorgi, D.: \[ \pi \] -calculus, internal mobility, and agent-passing calculi. In: Selected papers from TAPSOFT ’95, pp. 235–274. Elsevier (1996) · Zbl 0874.68103
[14] Sangiorgi, D.: Lazy functions and mobile processes. In: Proof, Language, and Interaction, pp. 691–720. The MIT Press (2000)
[15] Sangiorgi, D., Walker, D.: The Pi-Calculus: a theory of mobile processes. Cambridge University Press (2001) · Zbl 0981.68116
[16] van Bakel, S., Vigliotti, M.G.: An Implicative Logic based encoding of the \[ \lambda \] -calculus into the \[ \pi \] -calculus (2014). http://www.doc.ic.ac.uk/ svb/ · Zbl 1254.03021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.