Concurrent calculi, such as CCS, are defined in terms of labelled transition system; similarly, here we introduce the notion of net (or distributed) calculus, which is defined through a place/transition Petri net. As a first case study, a simple calculus of nets, called SCONE, is proposed, Relationships between SCONE and the subset of CCS without restriction and relabelling, called RCCS, are studied by showing that RCCS can be implemented in SCONE through a suitable mapping from the transition system for RCCS to net for SCONE. In particular, the complex CCS operation of global choice is implemented in terms of the SCONE finer grained operation of local choice, making explicit the fact that certain CCS transition are implemented as SCONE computations to be executed atomically. The result is a finite net implementation for RCCS agents. By making the quotient of the RCCS transition system w.r.t. the implementation mapping, we induce a truly concurrent semantics for RCCS. The second case study is then concerned with an extension dealing with restriction and relabelling. The resulting net calculus, called SCONE(+), is exploited as an implementation language for full CCS. The truly concurrent semantics induced by the implementation mapping is proved to coincide with the so-called ''permutation-of-transitions'' sematics.

ON THE IMPLEMENTATION OF CONCURRENT CALCULI IN NET CALCULI - 2 CASE-STUDIES

MONTANARI, UGO GIOVANNI ERASMO
1995

Abstract

Concurrent calculi, such as CCS, are defined in terms of labelled transition system; similarly, here we introduce the notion of net (or distributed) calculus, which is defined through a place/transition Petri net. As a first case study, a simple calculus of nets, called SCONE, is proposed, Relationships between SCONE and the subset of CCS without restriction and relabelling, called RCCS, are studied by showing that RCCS can be implemented in SCONE through a suitable mapping from the transition system for RCCS to net for SCONE. In particular, the complex CCS operation of global choice is implemented in terms of the SCONE finer grained operation of local choice, making explicit the fact that certain CCS transition are implemented as SCONE computations to be executed atomically. The result is a finite net implementation for RCCS agents. By making the quotient of the RCCS transition system w.r.t. the implementation mapping, we induce a truly concurrent semantics for RCCS. The second case study is then concerned with an extension dealing with restriction and relabelling. The resulting net calculus, called SCONE(+), is exploited as an implementation language for full CCS. The truly concurrent semantics induced by the implementation mapping is proved to coincide with the so-called ''permutation-of-transitions'' sematics.
Gorrieri, R; Montanari, UGO GIOVANNI ERASMO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/21767
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 10
social impact