Istituto di Scienza e Tecnologie dell'Informazione     
Degano P., De Nicola R., Montanari U. A partial ordering semantics for CCS. Gia' apparsa come TR-3/88, Universita' degli Studi di Pisa, dipartimento di informatica. Internal note IEI-B4-60, 1988.
A new operational semantics for "pure" CCS is proposed that considers the parallel operator as a first class 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 sub-agents, and the new derivations which relate sets of sub-agents describe their actions and their causal dependencies. The computations obtained by animating sets of sub-agents via the partial ordering derivation relation are "observed" either as interleaving or partial orderings of events. Interleavings coincide with Milner's many step derivations, and "linearizations" of partial orderings are all and only interleavings. In order to obtain more abstract semantics, we introduce two relations of partial ordering observational equivalence and congruence that preserve concurrency. These are finer than Milner's exactly in that they distinguish interleaving of sequential nondeterministic agents from their concurrent execution.

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