article

Expressiveness of Process Algebras

Author:

Joachim ParrowAuthors Info & Claims

Electronic Notes in Theoretical Computer Science (ENTCS), Volume 209

Pages 173 - 186

https://doi.org/10.1016/j.entcs.2008.04.011

Published: 01 April 2008 Publication History

Abstract

We examine ways to measure expressiveness of process algebras, and recapitulate and compare some related results from the literature.

References

[1]

Baeten, Jos C.M., Bergstra, Jan A. and Klop, Jan Willem, On the consistency of koomen's fair abstraction rule. Theor. Comput. Sci. v51. 129-176.

Digital Library

Google Scholar

[2]

Michael Baldamus, Joachim Parrow, and Björn Victor. Spi calculus translated to pi--calculus preserving may-tests. In LICS, pages 22--31. IEEE Computer Society, 2004

Crossref

Google Scholar

[3]

Baldamus, Michael, Parrow, Joachim and Victor, Björn, A fully abstract encoding of the pi-calculus with data terms. In: Caires, Luís, Italiano, Giuseppe F., Monteiro, Luís, Palamidessi, Catuscia, Yung, Moti (Eds.), Lecture Notes in Computer Science, volume 3580. Springer. pp. 1202-1213.

Crossref

Google Scholar

[4]

Cacciagrano, Diletta, Corradini, Flavio and Palamidessi, Catuscia, Separation of synchronous and asynchronous communication via testing. Electr. Notes Theor. Comput. Sci. v154 i3. 95-108.

Google Scholar

[5]

de Simone, Robert, Higher-level synchronising devices in meije-sccs. Theor. Comput. Sci. v37. 245-267.

Crossref

Google Scholar

[6]

Laneve, Cosimo and Victor, Björn, Solos in concert. In: Wiedermann, Jirí, van Emde Boas, Peter, Nielsen, Mogens (Eds.), Lecture Notes in Computer Science, volume 1644. Springer. pp. 513-523.

Crossref

Google Scholar

[7]

Nestmann, Uwe, What is a good encoding of guarded choice?. Inf. Comput. v156 i1--2. 287-319.

Crossref

Google Scholar

[8]

Nestmann, Uwe and Pierce, Benjamin C., Decoding choice encodings. Inf. Comput. v163 i1. 1-69.

Crossref

Google Scholar

[9]

Catuscia Palamidessi. Comparing the expressive power of the synchronous and the asynchronous pi-calculus. In POPL, pages 256--265, 1997

Crossref

Google Scholar

[10]

Palamidessi, Catuscia, Comparing the expressive power of the synchronous and asynchronous pi-calculi. Mathematical Structures in Computer Science. v13 i5. 685-719.

Crossref

Google Scholar

[11]

Catuscia Palamidessi, Vijay A. Saraswat, Frank D. Valencia, and Björn Victor. On the expressiveness of linearity vs persistence in the asychronous pi-calculus. In LICS, pages 59--68. IEEE Computer Society, 2006

Digital Library

Google Scholar

[12]

Parrow, Joachim, The expressive power of simple parallelism. In: Odijk, Eddy, Rem, Martin, Syre, Jean-Claude (Eds.), Lecture Notes in Computer Science, volume 366. Springer. pp. 389-405.

Crossref

Google Scholar

[13]

Parrow, Joachim, The expressive power of parallelism. Future Generation Computer Systems. v6. 271-285.

Crossref

Google Scholar

[14]

Parrow, Joachim, Trios in concert. In: Proof, Language and Interaction, Essays in Honour of Robin Milner, MIT Press. pp. 621-637.

Crossref

Google Scholar

[15]

Quaglia, Paola and Walker, David, On synchronous and asynchronous mobile processes. In: Tiuryn, Jerzy (Ed.), Lecture Notes in Computer Science, volume 1784. Springer. pp. 283-296.

Crossref

Google Scholar

[16]

Sangiorgi, Davide, From pi-calculus to higher-order pi-calculus -- and back. In: Gaudel, Marie-Claude, Jouannaud, Jean-Pierre (Eds.), Lecture Notes in Computer Science, volume 668. Springer. pp. 151-166.

Crossref

Google Scholar

[17]

Vaandrager, Frits W., Expressive results for process algebras. In: de Bakker, J.W., de Roever, Willem P., Rozenberg, Grzegorz (Eds.), Lecture Notes in Computer Science, volume 666. Springer. pp. 609-638.

Crossref

Google Scholar

[18]

Yoshida, Nobuko, Minimality and separation results on asynchronous mobile processes: Representability theorems by concurrent combinators (extended abstract). In: Sangiorgi, Davide, de Simone, Robert (Eds.), Lecture Notes in Computer Science, volume 1466. Springer. pp. 131-146.

Crossref

Google Scholar

[19]

Yoshida, Nobuko, Minimality and separation results on asynchronous mobile processes -- representability theorems by concurrent combinators. Theor. Comput. Sci. v274 i1--2. 231-276.

Crossref

Google Scholar

Cited By

View all

Bittner PSchultheiß AMoosherr BYoung JTeixeira LWalkingshaw EAtaei PThüm T(2024)On the Expressive Power of Languages for Static VariabilityProceedings of the ACM on Programming Languages10.1145/36897478:OOPSLA2(1018-1050)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689747
Peters KYoshida NSobocinski PLago UEsparza J(2024)Separation and Encodability in Mixed Choice Multiparty SessionsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662085(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662085
Peters KYoshida N(2024)Mixed choice in session typesInformation and Computation10.1016/j.ic.2024.105164298:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.ic.2024.105164
Show More Cited By

Index Terms

Expressiveness of Process Algebras
1. Theory of computation
  1. Logic
  2. Models of computation
    1. Computability

Recommendations

On the expressiveness of spider diagrams and commutative star-free regular languages

Spider diagrams provide a visual logic to express relations between sets and their elements, extending the expressiveness of Venn diagrams. Sound and complete inference systems for spider diagrams have been developed and it is known that they are ...
Commutative pseudo-equality algebras

Pseudo-equality algebras were initially introduced by Jenei and Kóródi as a possible algebraic semantic for fuzzy-type theory, and they have been revised by Dvureăźenskij and Zahiri under the name of JK-algebras. In this paper, we define and study the ...
Pseudo-BL algebras and pseudo-effect algebras

Pseudo-BL algebras and pseudo-effect algebras arose in two rather different fields: fuzzy logics and quantum logics. In this paper, by introducing the notion of pseudo-weak MV-effect algebra which is non-commutative generalization of weak MV-effect ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Electronic Notes in Theoretical Computer Science (ENTCS)

Electronic Notes in Theoretical Computer Science (ENTCS) Volume 209, Issue

April, 2008

210 pages

ISSN:1571-0661

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 April 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bittner PSchultheiß AMoosherr BYoung JTeixeira LWalkingshaw EAtaei PThüm T(2024)On the Expressive Power of Languages for Static VariabilityProceedings of the ACM on Programming Languages10.1145/36897478:OOPSLA2(1018-1050)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689747
Peters KYoshida NSobocinski PLago UEsparza J(2024)Separation and Encodability in Mixed Choice Multiparty SessionsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662085(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662085
Peters KYoshida N(2024)Mixed choice in session typesInformation and Computation10.1016/j.ic.2024.105164298:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.ic.2024.105164
Devriese DPatrignani MPiessens F(2022)Two Parametricities Versus Three Universal TypesACM Transactions on Programming Languages and Systems10.1145/353965744:4(1-43)Online publication date: 21-Sep-2022
https://dl.acm.org/doi/10.1145/3539657
Jacobs KDevriese DTimany A(2022)Purity of an ST monad: full abstraction by semantically typed back-translationProceedings of the ACM on Programming Languages10.1145/35273266:OOPSLA1(1-27)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527326
Cano MLópez HPérez JRueda C(2022)Session-based concurrency, declarativelyActa Informatica10.1007/s00236-021-00395-w59:1(1-87)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s00236-021-00395-w
Toninho BYoshida N(2021)On Polymorphic Sessions and FunctionsACM Transactions on Programming Languages and Systems10.1145/345788443:2(1-55)Online publication date: 10-Jun-2021
https://dl.acm.org/doi/10.1145/3457884
Jacobs KTimany ADevriese D(2021)Fully abstract from static to gradualProceedings of the ACM on Programming Languages10.1145/34342885:POPL(1-30)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434288
Ngondi GKoutavas VButterfield A(2021)Translation of CCS into CSP, Correct up to Strong BisimulationSoftware Engineering and Formal Methods10.1007/978-3-030-92124-8_14(243-261)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-92124-8_14
Patrignani MAhmed AClarke D(2019)Formal Approaches to Secure CompilationACM Computing Surveys10.1145/328098451:6(1-36)Online publication date: 4-Feb-2019
https://dl.acm.org/doi/10.1145/3280984
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

On the expressiveness of spider diagrams and commutative star-free regular languages

Commutative pseudo-equality algebras

Pseudo-BL algebras and pseudo-effect algebras

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations