Istituto di Scienza e Tecnologie dell'Informazione     
Degano P., De Nicola R., Montanari U. A partial ordering semantics for CCS. In: Theoretical Computer Science, vol. 75 pp. 223 - 262. North-Holland, 1990.
A new operational semantics for "pure" CCS is proposed that considers the parallel operator as a first c1ass one, and permits a description of the calculus in terms of partial orderings. The new semantics (also for unguarded agents) is given in the SOS style via the partial ordering derivation relation. CCS agents are decomposed into sets of sequential subagents. The new derivations relate sets or subagents, and describe their actions and the causal dependencies among them. The computations obtained by composing partial ordering derivations are "observed" either as interleaving or partial orderings of events. Interleavings coincide with Milner's many step derivations, and "linearizations" or partial orderings are all and only interleavings. Abstract semantics are obtained by introducing two relations of observational equivalence and congruence that preserve concurrency. These relations are finer than Milner's in that they distinguish interleaving of sequential nondeterministic agents from their concurrent execution.
Subject CCS

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional