*For the most recent entries see the
Petri Nets Newsletter.*

## Flow models of distributed computations - 3. Equivalent semantics for CCS.

Boudol, G.;
Castellani, I.
In:
*Information and Computation, Vol. 114, No. 2*, pages 247-314.
1994.

Abstract:
We introduce three notions of computation for processes described as CCS
(Calculus of Communicating Systems) terms. The first one uses an
adaptation of the equivalence by permutations of Berry and Levy. In this
setting, a computation is an equivalence class of sequences of
transitions, up to the permutation of independent steps. The second notion
of computation is given by means of an interpretation of CCS into a new
class of event structures, the flow event structures. This can be seen as
a reformulation of Winskel's semantics for CCS by means of stable event
structures. Here a computation is a configuration of an event structure.
Finally, our third notion of computation is determined by an
interpretation of CCS terms as Petri nets, and more precisely as flow
nets. Here a computation is a set of events that are firable in sequence
in the net. We then show that these three computation interpretations of
CCS coincide, in the sense that for a given term, the three domains of
computations are isomorphic. To this end we use an intermediary transition
system for CCS, where the past is recorded; this appears to be a system of
`trace computations' which provides another means of define the same
abstract domain of computations.

Keywords:
CCS, Petri nets, event structures, partial orders, transition systems.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*