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 / C. Laneve; A. Vitale. - STAMPA. - --:(2010), pp. 382-391. (Intervento presentato al convegno 25th Annual IEEE Symposium on Logic in Computer Science tenutosi a Edimburgo nel 11-14 July 2010).
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
