Classical concurrency in the DPO approach to graph rewriting, as defined by the shift equivalence construction, can also be represented by a graph process, a structure where concurrency and causal dependency are synthetically represented by a partial ordering of rewrites. Interestingly, all shift equivalent derivations, considered as diagrams in the category of graphs, have the same colimit, which moreover exactly corresponds to the graph process. This construction, due to Corradini, Montanari and Rossi, was originally defined for rules with injective right-hand morphisms. This condition turns out to be restrictive when graphs are used for modeling process calculi like ambients or fusion, where the coalescing of read-only items is essential. Recently, a paper by Habel, Muller and Plump considered again shift equivalence, extending classical results to non-injective rules. In this paper we look at the graph process-via-colimit approach: We propose and motivate its extension to non-injective rules in terms of existing computational models, and compare it with the aforementioned results.
Graph processes with fusions: Concurrency by colimits, again
GADDUCCI, FABIO;MONTANARI, UGO GIOVANNI ERASMO
2005-01-01
Abstract
Classical concurrency in the DPO approach to graph rewriting, as defined by the shift equivalence construction, can also be represented by a graph process, a structure where concurrency and causal dependency are synthetically represented by a partial ordering of rewrites. Interestingly, all shift equivalent derivations, considered as diagrams in the category of graphs, have the same colimit, which moreover exactly corresponds to the graph process. This construction, due to Corradini, Montanari and Rossi, was originally defined for rules with injective right-hand morphisms. This condition turns out to be restrictive when graphs are used for modeling process calculi like ambients or fusion, where the coalescing of read-only items is essential. Recently, a paper by Habel, Muller and Plump considered again shift equivalence, extending classical results to non-injective rules. In this paper we look at the graph process-via-colimit approach: We propose and motivate its extension to non-injective rules in terms of existing computational models, and compare it with the aforementioned results.File | Dimensione | Formato | |
---|---|---|---|
tHEbook.pdf
solo utenti autorizzati
Tipologia:
Versione finale editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
381.12 kB
Formato
Adobe PDF
|
381.12 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.