Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the expressiveness of infinite behavior and name scoping in process calculi
2004 (English)In: FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, PROCEEDINGS / [ed] Walukiewicz, I, BERLIN: SPRINGER , 2004, Vol. 2987, 226-240 p.Conference paper, Published paper (Refereed)
Abstract [en]

In the literature there are several CCS-like process calculi differing in the constructs for the specification of infinite behavior and in the scoping rules for channel names. In this paper we study various representatives of these calculi based upon both their relative expressiveness and the decidability of divergence. We regard any two calculi as being equally expressive iff for every process in each calculus, there exists a weakly bisimilar process in the other. By providing weak bisimilarity preserving mappings among the various variants, we show that in the context of relabeling-free and finite summation calculi: (1) CCS with parameterless (or constant) definitions is equally expressive to the variant with parametric definitions. (2) The CCS variant with replication is equally expressive to that with recursive expressions and static scoping. We also state that the divergence problem is undecidable for the calculi in (1) but decidable for those in (2). We obtain this from (un)decidability results by Busi, Gabbrielli and Zavattaro, and by showing the relevant mappings to be computable and to preserve divergence and its negation. From (1) and the well-known fact that parametric definitions can replace injective relabelings, we show that injective relabelings are redundant (i.e., derived) in CCS (which has constant definitions only).

Place, publisher, year, edition, pages
BERLIN: SPRINGER , 2004. Vol. 2987, 226-240 p.
Series
LECTURE NOTES IN COMPUTER SCIENCE, ISSN 0302-9743 ; 2987
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-43983ISI: 000189499900017Scopus ID: 2-s2.0-35048882486ISBN: 3-540-21298-1 (print)OAI: oai:DiVA.org:kth-43983DiVA: diva2:450877
Conference
7th International Conference on Foundations of Software Science and Computation Structures. Barcelona, SPAIN. MAR 30-APR 02, 2004
Note
QC 20111024Available from: 2011-10-24 Created: 2011-10-19 Last updated: 2011-10-24Bibliographically approved

Open Access in DiVA

No full text

Scopus
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 15 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf