Abstract
In [18, 19], we presented a theory of concurrent combinators for the asynchronous monadic π-calculus without match or summation operator [7, 16]. The system of concurrent combinators is based on a finite number of atoms and fixed interaction rules, but is as expressive as the original calculus, so that it can represent diverse interaction structures, including polyadic synchronous name passing [23] and input guarded summations [26]. The present paper shows that each of the five basic combinators introduced in [18] is indispensable to represent the whole computation, i.e. if one of the combinators is missing, we can no longer express the original calculus up to weak bisimilarity. Expressive power of several interesting subsystems of the asynchronous π-calculus is also measured by using appropriate subsets of the combinators and their variants. Finally as an application of the main result, we show there is no semantically sound encoding of the calculus into its proper subsystem under a certain condition.
Partially supported by EPSRC GR/K60701.
Full version available at: http://www.cogs.susx.ac.uk/users/nobuka/index.html.
Preview
Unable to display preview. Download preview PDF.
References
Abramsky, S., Interaction, Combinators, and Complexity, LFCS short course lecture, Edinburgh University, April, 1997.
Amadio, R., An asynchronous model of locality, failure, and process mobility. INRIA Research Report 3109, 1997.
Amadio, R., Casellani, I. and D., Sangiorgi, On Bisimulations for the Asynchronous π-calculus, Proc. CONCUR'96, LNCS 1119, pp.147–162, Springer-Verlag, 1996.
Barendregt, H., The Lambda Calculus: Its Syntax and Semantics. North Holland, 1984.
Berry, G. and Boudol, G., The Chemical Abstract Machine. TCS, vol 96, pp. 217–248, 1992.
Boreale, M., On the Expressiveness of Internal Mobility in Name-Passing Calculi, Proc. CONCUR'96, LNCS 1119, pp.163–178, Springer-Verlag, 1996.
Boudol, G., Asynchrony and π-calculus. INRIA Report 1702, INRIA, Sophia Antipolis, 1992.
Boudol, G., Some chemical abstract machines, Proceedings of the REX School/Workshop “A Decade of Concurrency”, LNCS 803, pp.92–123, 1994.
Fournet, C. et al., A Calculus for Mobile Agents, CONCUR'96, LNCS 1119, pp.406–421, Springer-Verlag, 1996.
Danos, V., Herbelin, H. and Regnier, L., Games Semantics and Abstract Machines. LICS'96, 1996.
Honda, K., Two Bisimilarities in Ν-calculus, Keio Technical Report, 92-002, 1992.
Honda, K., Notes on P-Algebra (1): Process Structure. Proc. TPPP'94, LNCS 907, pp.25–44, Springer-Verlag, 1995.
Honda, K., Process Structure, 49 pp, a typescript. Submitted for publication, March, 1997. Available from http://www.dcs.ed.ac.uk/home/kohei.
Honda, K., Notes on Undirected Action Structure, a typescript, March, 1997. Available from http://www.dcs.ed.ac.uk/home/kohei.
Honda, K. and Tokoro, M., A Small Calculus for Concurrent Objects, in OOPS Messenger, 2(2):50–54, Association for Computing Machinery, 1991.
Honda, K. and Tokoro, M., An Object Calculus for Asynchronous Communication. ECOOP'91, LNCS 512, pp.133–147, Springer-Verlag 1991.
Honda, K. and Yoshida, N., On Reduction-Based Process Semantics. TCS, pp.437–486, No.151, North-Holland, 1995.
Honda, K. and Yoshida, N., Combinatory Representation of Mobile Processes. POPL'94, pp.348–360, ACM Press, 1994.
Honda, K. and Yoshida, N., Replication in Concurrent Combinators, TACS'94, LNCS 789, pp.786–805, Springer, 1994.
Full version of [18]. To appear as a technical report of Sussex University, 1998.
Merro, M. and Sangiorgi, D., On asynchrony in name-passing calculi, ICALP'98, 1998.
Milner, R., Functions as Processes. MSCS, 2(2), pp.119–146, 1992.
Milner, R., Polyadic π-Calculus, Logic and Algebra of Specification, Springer-Verlag, 1992.
Milner, R., Action structures and the π-calculus, Proc. of Advanced Study Institute on Proof and Computation, Marktoberdorf, 1993.
Milner, R., Parrow, J.G. and Walker, D.J., A Calculus of Mobile Processes, Information and Computation 100(1), pp.1–77, 1992.
Nestmann, U. and Pierce, B., Decoding choice encodings, Proc. CONCUR'96, LNCS 1119, pp.179–194, Springer-Verlag, 1996.
Odersky, M., Polarized Name Passing. FST/TCS'15, LNCS, Springer-Verlag, 1995.
Palamidessi, C., Comparing the Expressive Power of the Synchronous and the Asynchronous π-calculus, POPL'97, pp. 256–265, ACM press, 1997.
Parrow, J., The Expressive Power of Parallelism. Future Generation Computer Systems, 6:271–285, 1990.
Parrow, J., Trios in Concert. Festschrift in honour of Robin Milner, MIT Press, 1998.
Parrow, J. and Victor, B., The Fusion Calculus: Expressiveness and Symmetry in Mobile Processes. LICS'98, 1998.
Parrow, J. and Sangiorgi, D., Algebraic Theories for Name-Passing Calculi, Research Report ECSLFCS-93-262, Department of Computer Science, University of Edinburgh 1993.
Pierce, B. and Turner, D., Pict: A Programming Language Based on the Pi-calculus, Indiana University, CSCI Technical Report, 476, March, 1997.
Raja, N. and Shyamasundar, R.K., Combinatory Formulations of Concurrent Languages, TOPLAS, Vol. 19, No. 6, pp.899–915, ACM Press, 1997.
Riely, J. and Hennessy, M., A Typed Language for Distibuted Mobile Processes. POPL'98, pp.378–390, ACM Press, 1998.
Sangiorgi, D., Expressing Mobility in Process Algebras: First Order and Higher Order Paradigms. Ph.D. Thesis, University of Edinburgh, 1992.
Turner, D.A., A New Implementation Technique for Applicative Languages., Software-Practice and Experience 9, pp.31–49, 1979.
Walker, D., Objects in the π-calculus. Information and Computation, Vol. 116, pp.253–271, 1995.
Yoshida, N., Graph Notation for Concurrent Combinators, TPPP'94, LNCS 907, pp.393–412, Springer-Verlag, 1995.
Yoshida, N., Graph Types for Monadic Mobile Processes, FST/TCS'16, LNCS 1180, pp. 371–386, Springer-Verlag, 1996. Full version as LFCS Technical Report, ECS-LFCS-96-350, 1996.
Yoshida, N., Full version of this paper. The first version in Oct, 1997. Revised in Feb, 1998. pp.40. Available from http://www.cogs.susx.ac.uk/users/nobuka/index.html. To appear as a technical report of Sussex University, 1998.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yoshida, N. (1998). Minimality and separation results on asynchronous mobile processes. In: Sangiorgi, D., de Simone, R. (eds) CONCUR'98 Concurrency Theory. CONCUR 1998. Lecture Notes in Computer Science, vol 1466. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055620
Download citation
DOI: https://doi.org/10.1007/BFb0055620
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64896-3
Online ISBN: 978-3-540-68455-8
eBook Packages: Springer Book Archive