Technical Report 2004-002

On the Expressiveness of CCS-like Calculi

Pablo Giambiagi, Gerardo Schneider, and Frank D. Valencia

January 2004

Abstract:

In the literature there are several CCS-like process calculi, or CCS variants, differing in the constructs for the specification of infinite behavior and in the scoping rules w.r.t. channel names. In this paper we study various representatives of these calculi based upon both their relative expressiveness and the decidability of divergence (i.e., the existence of a divergent computation). 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 scope. We also state that the divergence problem is undecidable for the calculi in (1) but decidable for those in (2). We obtain this from previous (un)decidability results 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).

Available as compressed Postscript (314 kB)

Download BibTeX entry.