zbMATH — the first resource for mathematics

On the expressiveness of symmetric communication. (English) Zbl 06667705
Sampaio, Augusto (ed.) et al., Theoretical aspects of computing – ICTAC 2016. 13th international colloquium, Taipei, Taiwan, ROC, October 24–31, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-46749-8/pbk; 978-3-319-46750-4/ebook). Lecture Notes in Computer Science 9965, 139-157 (2016).
Summary: The expressiveness of communication primitives has been explored in a common framework based on the \(\pi\)-calculus by considering four features: synchronism, arity, communication medium, and pattern-matching. These all assume asymmetric communication between input and output primitives, however some calculi consider more symmetric approaches to communication such as fusion calculus and concurrent pattern calculus. Symmetry can be considered either as supporting exchange of information between an action and co-action, or as unification of actions. By means of possibility/impossibility of encodings, this paper shows that the exchange approach is related to, or more expressive than, many previously considered languages. Meanwhile, the unification approach is more expressive than some, but mostly unrelated to, other languages.
For the entire collection see [Zbl 1347.68012].

68Qxx Theory of computing
Full Text: DOI
[1] Bengtson, J., Johansson, M., Parrow, J., Victor, B.: Psi-calculi: a framework for mobile processes with nominal data and logic. Log. Methods Comput. Sci. 7(1) (2011) · Zbl 1213.68399
[2] Bengtson, J., Parrow, J.: Formalising the pi-calculus using nominal logic. Log. Methods Comput. Sci. 5(2) (2009) · Zbl 1168.68030
[3] Boudol, G.: Notes on algebraic calculi of processes. In: Apt, K.R. (ed.) Logics and Models of Concurrent Systems, pp. 261–303. Springer, New York (1985) · doi:10.1007/978-3-642-82453-1_9
[4] Busi, N., Gorrieri, R., Zavattaro, G.: On the expressiveness of Linda coordination primitives. Inf. Comput. 156(1–2), 90–121 (2000) · Zbl 1046.68616 · doi:10.1006/inco.1999.2823
[5] Carbone, M., Maffeis, S.: On the expressive power of polyadic synchronisation in \[ \pi \] -calculus. Nordic J. Comput. 10(2), 70–98 (2003) · Zbl 1062.68077
[6] de Boer, F.S., Palamidessi, C.: Concurrent logic programming: asynchronism and language comparison. In: Proceedings of the 1990 North American Conference on Logic Programming, pp. 175–194. MIT Press, Cambridge (1990)
[7] de Boer, F.S., Palamidessi, C.: Embedding as a tool for language comparison. Inf. Comput. 108(1), 128–157 (1994) · Zbl 0788.68014 · doi:10.1006/inco.1994.1004
[8] Fournet, C., Gonthier, G.: The reflexive cham and the join-calculus. In: Proceedings of the 23rd ACM Symposium on Principles of Programming Languages, pp. 372–385. ACM Press (1996) · doi:10.1145/237721.237805
[9] Gelernter, D.: Generative communication in Linda. ACM Trans. Program. Lang. Syst. 7(1), 80–112 (1985) · Zbl 0559.68030 · doi:10.1145/2363.2433
[10] Given-Wilson, T.: Concurrent Pattern Unification. Ph.D. thesis, University of Technology, Sydney, Australia (2012)
[11] Given-Wilson, T.: An intensional concurrent faithful encoding of Turing machines. In: Proceedings of the ICE 2014, Berlin, Germany, 6 June 2014, pp. 21–37 (2014) · doi:10.4204/EPTCS.166.4
[12] Given-Wilson, T.: On the expressiveness of intensional communication. In: Proceedings of EXPRESS/SOS, Rome, Italie, September 2014 · Zbl 1432.68307 · doi:10.4204/EPTCS.160.4
[13] Given-Wilson, T., Gorla, D.: Pattern matching and bisimulation. In: Nicola, R., Julien, C. (eds.) COORDINATION 2013. LNCS, vol. 7890, pp. 60–74. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-38493-6_5 · Zbl 06267973 · doi:10.1007/978-3-642-38493-6_5
[14] Given-Wilson, T., Gorla, D., Jay, B.: A concurrent pattern calculus. Log. Methods Comput. Sci. 10(3) (2014) · Zbl 1338.68202
[15] Given-Wilson, T., Legay, A.: On the expressiveness of joining. In: ICE 2015, Grenoble, France, June 2015 · Zbl 06667705
[16] Gorla, D.: Comparing communication primitives via their relative expressive power. Inf. Comput. 206(8), 931–952 (2008) · Zbl 1169.68009 · doi:10.1016/j.ic.2008.05.001
[17] Gorla, D.: A taxonomy of process calculi for distribution and mobility. Distrib. Comput. 23(4), 273–299 (2010) · Zbl 1231.68169 · doi:10.1007/s00446-010-0120-6
[18] Gorla, D.: Towards a unified approach to encodability and separation results for process calculi. Inf. Comput. 208(9), 1031–1053 (2010) · Zbl 1209.68336 · doi:10.1016/j.ic.2010.05.002
[19] Jay, B.: Pattern Calculus: Computing with Functions and Data Structures. Springer, Heidelberg (2009) · Zbl 1215.68055 · doi:10.1007/978-3-540-89185-7
[20] Jay, B., Given-Wilson, T.: A combinatory account of internal structure. J. Symbol. Logic 76(3), 807–826 (2011) · Zbl 1248.03025 · doi:10.2178/jsl/1309952521
[21] Lanese, I., Pérez, J.A., Sangiorgi, D., Schmitt, A.: On the expressiveness of polyadic and synchronous communication in higher-order process calculi. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 442–453. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-14162-1_37 · Zbl 1288.68183 · doi:10.1007/978-3-642-14162-1_37
[22] Lanese, I., Vaz, C., Ferreira, C.: On the expressive power of primitives for compensation handling. In: Gordon, A.D. (ed.) ESOP 2010. LNCS, vol. 6012, pp. 366–386. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-11957-6_20 · Zbl 1260.68102 · doi:10.1007/978-3-642-11957-6_20
[23] Milner, R.: The polyadic \[ \pi \] -calculus: a tutorial. In: Logic and Algebra of Specification, vol. 94. Series F. NATO ASI, 203–246. Springer, Heidelberg (1993)
[24] Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes I & II. Inf. Comput. 100(1), 1–77 (1992) · Zbl 0752.68036 · doi:10.1016/0890-5401(92)90008-4
[25] Nielsen, L., Yoshida, N., Honda, K.: Multiparty symmetric sum types. In: Proceedings of EXPRESS, pp. 121–135 (2010) · doi:10.4204/EPTCS.41.9
[26] Palamidessi, C.: Comparing the expressive power of the synchronous and asynchronous pi-calculi. Math. Struct. Comp. Sci. 13(5), 685–719 (2003) · doi:10.1017/S0960129503004043
[27] Parrow, J.: Expressiveness of process algebras. Electron. Not. Theoret. Comput. Sci. 209, 173–186 (2008) · Zbl 1279.68264 · doi:10.1016/j.entcs.2008.04.011
[28] Parrow, J., Victor, B.: The fusion calculus: expressiveness and symmetry in mobile processes. In: Proceedings of 13th Annual IEEE Symposium on Logic in Computer Science, pp. 176–185, June 1998 · doi:10.1109/LICS.1998.705654
[29] Peters, K.: Translational expressiveness: comparing process calculi using encodings. Ph.D. thesis, Technische Universität Berlin, Fakultät IV, Germany (2012)
[30] Shapiro, E.: Separating concurrent languages with categories of language embeddings. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 198–208. ACM, New York (1991) · doi:10.1145/103418.103423
[31] van Glabbeek, R.J.: Musings on encodings and expressiveness. In: Proceedings of EXPRESS/SOS. EPTCS, vol. 89, pp. 81–98 (2012) · doi:10.4204/EPTCS.89.7
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.