Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Verification of Concurrent Programs on Weak Memory Models Read chapter Read first chapter

2016 | OriginalPaper | Chapter

On the Expressiveness of Symmetric Communication

Authors : Thomas Given-Wilson, Axel Legay

Published in: Theoretical Aspects of Computing – ICTAC 2016

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Schedulers and Finishers: On Generating the Behaviours of an Event Structure
next chapter Towards MC/DC Coverage of Properties Specification Patterns
Literature
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)
2.
Bengtson, J., Parrow, J.: Formalising the pi-calculus using nominal logic. Log. Methods Comput. Sci. 5(2) (2009)
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)
4.
Busi, N., Gorrieri, R., Zavattaro, G.: On the expressiveness of Linda coordination primitives. Inf. Comput. 156(1–2), 90–121 (2000)MathSciNetCrossRefMATH
5.
Carbone, M., Maffeis, S.: On the expressive power of polyadic synchronisation in \(\pi \)-calculus. Nordic J. Comput. 10(2), 70–98 (2003)MathSciNetMATH
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.
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)
9.
Gelernter, D.: Generative communication in Linda. ACM Trans. Program. Lang. Syst. 7(1), 80–112 (1985)CrossRefMATH
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)
12.
Given-Wilson, T.: On the expressiveness of intensional communication. In: Proceedings of EXPRESS/SOS, Rome, Italie, September 2014
13.
14.
Given-Wilson, T., Gorla, D., Jay, B.: A concurrent pattern calculus. Log. Methods Comput. Sci. 10(3) (2014)
15.
Given-Wilson, T., Legay, A.: On the expressiveness of joining. In: ICE 2015, Grenoble, France, June 2015
16.
17.
18.
Gorla, D.: Towards a unified approach to encodability and separation results for process calculi. Inf. Comput. 208(9), 1031–1053 (2010)MathSciNetCrossRefMATH
19.
Jay, B.: Pattern Calculus: Computing with Functions and Data Structures. Springer, Heidelberg (2009)CrossRefMATH
20.
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 CrossRef
22.
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.
25.
Nielsen, L., Yoshida, N., Honda, K.: Multiparty symmetric sum types. In: Proceedings of EXPRESS, pp. 121–135 (2010)
26.
Palamidessi, C.: Comparing the expressive power of the synchronous and asynchronous pi-calculi. Math. Struct. Comp. Sci. 13(5), 685–719 (2003)MathSciNetCrossRef
27.
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
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)
31.
van Glabbeek, R.J.: Musings on encodings and expressiveness. In: Proceedings of EXPRESS/SOS. EPTCS, vol. 89, pp. 81–98 (2012)
Metadata
Title
On the Expressiveness of Symmetric Communication
Authors
Thomas Given-Wilson
Axel Legay
Copyright Year
2016
Book
Theoretical Aspects of Computing – ICTAC 2016

Print ISBN: 978-3-319-46749-8

Electronic ISBN: 978-3-319-46750-4

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-46750-4_9

Premium Partner

    Image Credits