Abstract
A simple, yet Turing powerful, calculus based on generative communication is introduced; among its primitives, it contains a conditional input operation that tests for presence (or absence) of an output, reminiscent of the inp predicate of Linda. We study three different operational semantics for the output operation, called instantaneous, ordered and unordered. The associated behavioural semantics are obtained as the coarsest congruence contained in the corresponding strong barbed semantics. We prove that when the output operation is instantaneous, the obtained semantics is a sort of asynchronous bisimulation; on the contrary, for the ordered semantics, as well as for the unordered one, the resulting semantics is a small variant of the classic (synchronous) bisimulation. A further result is that the language under unordered semantics is no more Turing powerful, hence the language becomes strictly less expressive.
Work supported by Esprit Working Group Coordina.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Amadio, I. Castellani, and D. Sangiorgi. On Bisimulations for the Asynchronous π-Calculus. In Proc. CONCUR'96, volume 1119 of LNCS, pages 147–162, Springer Verlag, 1996.
G. Boudol. Asynchrony and the π-calculus. Technical Report 1702, INRIA, Sophia-Antipolis, 1992.
N. Busi and R. Gorrieri. A Petri Net Semantics for π-calculus. In Proc. CONCUR'95, volume 962 of LNCS, pages 145–159, Springer Verlag, 1995.
N. Busi, R. Gorrieri, and G. Zavattaro. A Truly Concurrent view of Linda Interprocess Communication. Technical Report UBLCS-97-02, Department of Computer Science, University of Bologna, February 1997.
N. Busi, R. Gorrieri, and G. Zavattaro. On the Turing Equivalence of Linda Coordination Primitives. Technical Report UBLCS-97-05, Department of Computer Science, University of Bologna, May 1997.
N. Busi, R. Gorrieri, and G. Zavattaro, A Process Algebraic View of Linda Coordination Primitives. To appear in Theoretical Computer Science. Available as Technical Report UBLCS-97-06, Department of Computer Science, University of Bologna, May 1997.
N. Busi and G.M. Pinna. A Causal Semantics for Contextual P/T nets. In Proc. ICTCS'95, 311–325, World Scientific, 1995.
P. Ciancarini, R. Gorrieri, and G. Zavattaro. Towards a Calculus for Generative Communication. In Proc. 1st IFIP Conf. on FMOODS'96, pages 283–297. Chapman & Hall, 1996.
D. Gelernter. Generative Communication in Linda. ACM Transactions on Programming Languages and Systems, 7(1):80–112, 1985.
D. Gelernter and N. Carriero. Coordination Languages and their Significance. Communications of the ACM, 35(2):97–107, 1992.
J.F. Groote. Transition system specifications with negative premises. Theoretical Computer Science, 118:263–299, 1993.
M. Hansen, J. Kleist, and H. Hüttel. Bisimulations for Asynchronous Mobile Processes. In Proc. Tbilisi Symposium on Language, Logic, and Computation, 1995.
K. Honda and M. Tokoro. An Object Calculus for Asynchronous Communication. In Proc. ECOOP '91, volume 512 of LNCS, pages 133–147. Springer Verlag, 1991.
R. Milner. Communication and Concurrency. Prentice-Hall, 1989.
R. Milner and D. Sangiorgi. Barbed Bisimulation. In Proc. ICALP'92, volume 623 of LNCS, pages 685–695, Springer Verlag, 1992.
M. L. Minsky. Computation: finite and infinite machines. Prentice-Hall, Englewood Cliffs, 1967.
U. Montanari and F. Rossi. Contextual Nets. Acta Informatica, 32(6):545–596, 1995.
J. E. Narem. An Informal Operational Semantics of C-Linda V2.3.5. Technical Report YALEU/DCS/TR-839, Department of Computer Science, Yale University, December 1990.
Scientific Computing Associates. Linda: User's guide and reference manual. Scientific Computing Associates, 1995.
J. C. Shepherdson and J. E. Sturgis. Computability of recursive functions. Journal of the ACM, 10:217–255, 1963.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Busi, N., Gorrieri, R., Zavattaro, G. (1997). Three semantics of the output operation for generative communication. In: Garlan, D., Le Métayer, D. (eds) Coordination Languages and Models. COORDINATION 1997. Lecture Notes in Computer Science, vol 1282. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63383-9_82
Download citation
DOI: https://doi.org/10.1007/3-540-63383-9_82
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63383-9
Online ISBN: 978-3-540-69527-1
eBook Packages: Springer Book Archive