We introduce a new criterion to discern the relative expressiveness of process calculi. Intuitively, a calculus is replacement free if replacing a sub-process that cannot perform any visible action by an arbitrary one never affects the capability of the resulting process to perform a visible action. By relying on two slightly different formulations of our criterion we partition the set of process calculi into three classes. Then, we prove that no suitable encodings between any two of such classes exist; hence calculi belonging to different classes have different relative expressiveness. Finally, we classify many well-known variants of the mainstream calculi CCS and the π-calculus, thus demonstrating their expressiveness gaps.
Replacement freeness: A criterion for separating process calculi / Pugliese, Rosario; Tiezzi, Francesco. - In: THE JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING. - ISSN 2352-2208. - STAMPA. - 116:(2020), pp. 1-33. [10.1016/j.jlamp.2020.100579]
Replacement freeness: A criterion for separating process calculi
Pugliese, Rosario;Tiezzi, Francesco
2020
Abstract
We introduce a new criterion to discern the relative expressiveness of process calculi. Intuitively, a calculus is replacement free if replacing a sub-process that cannot perform any visible action by an arbitrary one never affects the capability of the resulting process to perform a visible action. By relying on two slightly different formulations of our criterion we partition the set of process calculi into three classes. Then, we prove that no suitable encodings between any two of such classes exist; hence calculi belonging to different classes have different relative expressiveness. Finally, we classify many well-known variants of the mainstream calculi CCS and the π-calculus, thus demonstrating their expressiveness gaps.File | Dimensione | Formato | |
---|---|---|---|
JLAMP2020.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
951.12 kB
Formato
Adobe PDF
|
951.12 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.