The true concurrency of differential interaction nets

We analyse the reduction of differential interaction nets from the point of view of so-called ‘true concurrency,’ that is, employing a non-interleaving model of parallelism. More precisely, we associate with each differential interaction net an event structure describing its reduction. We show how d...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical structures in computer science 2018-08, Vol.28 (7), p.1097-1125
Main Author: MAZZA, DAMIANO
Format: Article
Language:English
Subjects:
Coding
Concurrency
Confusion
Differential calculus
Magnesium
Reduction
Semantics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We analyse the reduction of differential interaction nets from the point of view of so-called ‘true concurrency,’ that is, employing a non-interleaving model of parallelism. More precisely, we associate with each differential interaction net an event structure describing its reduction. We show how differential interaction nets are only able to generate confusion-free event structures, and we argue that this is a serious limitation in terms of the concurrent behaviours they may express. In fact, confusion is an extremely elementary phenomenon in concurrency (for example, it already appears in CCS with just prefixing and parallel composition) and we show how its presence is preserved by any encoding respecting the degree of distribution and the reduction semantics. We thus infer that no reasonably expressive process calculus may be satisfactorily encoded in differential interaction nets. We conclude with an analysis of one such encoding proposed by Ehrhard and Laurent, and argue that it does not contradict our claims, but rather supports them.
ISSN:0960-1295
1469-8072
DOI:10.1017/S0960129516000402