# zbMATH — the first resource for mathematics

On the expressiveness of interaction. (English) Zbl 1191.68436
Summary: Subbisimilarity is proposed as a general tool to classify the relative expressive power of process calculi. The expressiveness of several variants of CCS is compared in terms of the subbisimilarity relationship. Similar investigation is also carried out for the variants of the pi calculus. The relative expressiveness of the different forms of the choice operation and the different ways of introducing infinite behaviors are systematically studied in both the frameworks of CCS and pi. Some issues concerning the expressiveness of both CCS and pi are clarified. Several open problems are solved along the way. The subbisimilarity approach and the relative expressiveness results are applied to show the independence of the operators of the pi calculus. The definition of the subbisimilarity relationship can be further strengthened with computational requirement, leading to a uniform treatment of computation and interaction.

##### MSC:
 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
##### Keywords:
process calculus; expressiveness; bisimulation
Full Text:
##### References:
 [1] Abramsky, S., The lazy lambda calculus, (), 65-116 [2] Alsuwaiyel, M., Algorithm design techniques and analysis, (1999), World Scientific · Zbl 1216.68002 [3] Amadio, R.; Castellani, I.; Sangiorgi, D., On bisimulations for the asynchronous $$\pi$$-calculus, (), 147-162 [4] Baeten, J.; Weijland, W., () [5] Barendregt, H., The lambda calculus: its syntax and semantics, () · Zbl 0467.03010 [6] G. Boudol, Asynchrony and the $$\pi$$-calculus, Technical Report RR-1702, INRIA Sophia-Antipolis, 1992 [7] Busi, N.; Gabbrielli, M.; Zavattaro, G., Replication vs recursive definitions in channel based calculi, (), 133-144 · Zbl 1039.68082 [8] Busi, N.; Gabbrielli, M.; Zavattaro, G., Comparing recursion, replication and iteration in process calculi, (), 307-319 · Zbl 1098.68086 [9] Busi, N.; Zavattaro, G., On the expressive power of movement and restriction in pure mobile ambients, Theoretical computer science, 322, 477-515, (2004) · Zbl 1071.68072 [10] Cacciagrano, D.; Corradini, F.; Aranda, J.; Valencia, F., Linearity, persistence and testing semantics in the asynchronous pi-calculus, (), 59-84 · Zbl 1277.68167 [11] X. Cai, Y. Fu, The $$\lambda$$-calculus in the $$\pi$$-calculus, 2009. The paper is downloadable at http://basics.sjtu.edu.cn/ yuxi/papers · Zbl 1223.68073 [12] Cardelli, L.; Gordon, A., Mobile ambients, Theoretical computer science, 240, 177-213, (2000) · Zbl 0954.68108 [13] Davey, B.; Priestley, H., Introduction to lattices and order, (1990), Cambridge University Press · Zbl 0701.06001 [14] De Nicola, R.; Hennessy, M., Testing equivalence for processes, Theoretical computer science, 34, 83-133, (1984) · Zbl 0985.68518 [15] Dong, X.; Fu, Y., Extensional net theory, (2009) [16] van Emde Boas, P., Machine models and simulaitons, () · Zbl 0468.68054 [17] Finkel, A.; Schnoebelen, Ph., Well-structured transition system everywhere, Theoretical computer science, 256, 63-92, (2001) · Zbl 0973.68170 [18] Fu, Y., On quasi-open bisimulation, Theoretical computer science, 338, 96-126, (2005) · Zbl 1077.68060 [19] Fu, Y., Fair ambients, Acta informatica, 43, 535-594, (2007) · Zbl 1111.68082 [20] Y. Fu, Theory of interaction, Working Paper, 2009 [21] Y. Fu, Theory of value passing calculus, Working Paper, 2009 [22] Fu, Y.; Yang, Z., Tau laws for pi calculus, Theoretical computer science, 308, 55-130, (2003) · Zbl 1071.68075 [23] Y. Fu, H. Zhu, Theory of name passing calculus, Working Paper, 2009 [24] Girard, J., Linear logic, Theoretical computer science, 50, 1-102, (1987) · Zbl 0625.03037 [25] van Galbbeek, R., Linear time — branching time spectrum II, (), 66-81 [26] van Glabbeek, R.; Weijland, W., Branching time and abstraction in bisimulation semantics, (), 613-618 · Zbl 0882.68085 [27] Giambiagi, P.; Schneider, G.; Valencia, F., On the expressiveness of infinite behavior and name scoping in process calculi, (), 226-240 · Zbl 1126.68500 [28] Gorla, D., Towards a unified approach to encodability and separation results for process calculi, (), 492-507 · Zbl 1160.68466 [29] Gorla, D., Comparing communication primitives via their relative expressive power, Information and computation, 206, 931-952, (2008) · Zbl 1169.68009 [30] Gorla, D., On the relative power of ambient-based calculi, (), 141-156 [31] Gorla, D., On the relative power of calculi for mobility, () · Zbl 1337.68182 [32] Hennessy, M., An algebraic theory of processes, (1988), MIT Press Cambridge, MA [33] Hennessy, M.; Lin, H., Symbolic bisimulations, Theoretical computer science, 138, 137-161, (1995) · Zbl 0874.68187 [34] Honda, K.; Tokoro, M., An object calculus for asynchronous communications, (), 133-147 [35] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Publishing Company · Zbl 0426.68001 [36] Ingolfsdottir, A.; Lin, H., A symbolic approach to value-passing processes, (), (Chapter 7) · Zbl 1027.68092 [37] Kruskal, J., The theory of well ordering: A frequently discovered concept, Journal of combinatorial theory, series A, 13, 297-305, (1972) · Zbl 0244.06002 [38] I. Lanese, J. Perez, D. Sangiorgi, A. Schmitt, On the expressiveness and decidability of higher-order process calculi, in: LICS’08, 2008, pp. 145-155 · Zbl 1238.68100 [39] Milner, R., Communication and concurrency, (1989), Prentice Hall · Zbl 0683.68008 [40] Milner, R., Functions as processes, Mathematical structures in computer science, 2, 119-146, (1992) · Zbl 0773.03012 [41] Milner, R., Elements of interaction, Communication of the ACM, 78-89, (1993) [42] Maffeis, S.; Phillips, I., On the computational strength of pure ambient calculi, Theoretical computer science, 330, 501-551, (2005) · Zbl 1078.68108 [43] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, Information and computation, 100, (1992), 1-40 (Part I), 41-77 (Part II) · Zbl 0752.68036 [44] Milner, R., The polyadic $$\pi$$-calculus: A tutorial, () [45] Milner, R.; Sangiorgi, D., Barbed bisimulation, (), 685-695 [46] Nestmann, U.; Pierce, B., Decoding choice encodings, (), 179-194 [47] Nestmann, U., What is a good encoding of guarded choices?, Information and computation, 156, 287-319, (2000) · Zbl 1046.68625 [48] Nestmann, U., Welcome to the jungle: A subjective guide to mobile process calculi, (), 52-63 · Zbl 1151.68548 [49] Palamidessi, C., Comparing the expressive power of the synchronous and the asynchronous $$\pi$$-calculus, Mathematical structures in computer science, 13, 685-719, (2003) [50] Park, D., Concurrency and automata on infinite sequences, (), 167-183 [51] Phillips, I.; Vigliotti, M., Leader election in rings of ambient processes, Theoretical computer science, 356, 468-494, (2006) · Zbl 1092.68068 [52] Priese, L., On the concept of simulation in asynchronous, concurrent systems, (), 85-92 [53] Palamidessi, C.; Saraswat, V.; Valencia, F.; Victor, B., On the expressiveness of linearity vs persistence in the asynchronous pi calculus, (), 59-68 [54] Sangiorgi, D., $$\pi$$-calculus, internal mobility and agent-passing calculi, Theoretical computer science, 167, 235-274, (1996) · Zbl 0874.68103 [55] Sangiorgi, D., A theory of bisimulation for $$\pi$$-calculus, Acta informatica, 3, 69-97, (1996) · Zbl 0835.68072 [56] Sangiorgi, D., Bisimulation for higher order process calculi, Information and comptation, 131, 141-178, (1996) · Zbl 0876.68042 [57] Sangiorgi, D., On the origin of bisimulation and coinduction, () [58] Sipser, M., Introduction to theory of computation, (1997), PWS Publishing Company · Zbl 1169.68300 [59] Sangiorgi, D.; Walker, D., On barbed equivalence in $$\pi$$-calculus, (), 292-304 · Zbl 1006.68090 [60] Sangiorgi, D.; Walker, D., The pi calculus—A theory of mobile processes, (2001), CUP · Zbl 0981.68116 [61] Thomsen, B., A theory of higher order communicating systems, Information and computation, 116, 38-57, (1995) · Zbl 0823.68061 [62] Vigliotti, M.; Phillips, I.; Palamidessi, C., Tutorial on separation results in process calculi via leader election, Theoretical computer science, 388, 267-289, (2007) · Zbl 1143.68056 [63] Walker, D., Bisimulation and divergence, Information and computation, 85, 202-241, (1990) · Zbl 0713.68036 [64] Wegener, I., Complexity theory, (2005), Spronger-Verlag
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.