@TechReport{ it:2004-002,
author = {Pablo Giambiagi and Gerardo Schneider and Frank D.
Valencia},
title = {On the Expressiveness of {CCS}-like Calculi},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Computer Systems},
year = {2004},
number = {2004-002},
month = jan,
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).}
}