A synchronization is a mechanism allowing two or more processes to perform actions at the same time. We study the expressive power of synchronizations gathering more and more processes simultaneously. We demonstrate the non-existence of a uniform, fully distributed translation of Milner's CCS with synchronizations of $n+1$ processes into CCS with synchronizations of $n$ processes that retains a "reasonable'' semantics. We then extend our study to CCS with symmetric synchronizations allowing a process to perform both inputs and outputs at the same time. We demonstrate that synchronizations containing more than three input/output items are encodable in those with three items, while there is an expressivity gap between three and two.

The Expressive Power of Synchronizations

LANEVE, COSIMO;VITALE, ANTONIO
2010

Abstract

A synchronization is a mechanism allowing two or more processes to perform actions at the same time. We study the expressive power of synchronizations gathering more and more processes simultaneously. We demonstrate the non-existence of a uniform, fully distributed translation of Milner's CCS with synchronizations of $n+1$ processes into CCS with synchronizations of $n$ processes that retains a "reasonable'' semantics. We then extend our study to CCS with symmetric synchronizations allowing a process to perform both inputs and outputs at the same time. We demonstrate that synchronizations containing more than three input/output items are encodable in those with three items, while there is an expressivity gap between three and two.
Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010
382
391
C. Laneve; A. Vitale
File in questo prodotto:
Eventuali allegati, non sono esposti

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: https://hdl.handle.net/11585/95954
 Attenzione

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

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