Parallel and sequential independence are central concepts in the concurrency theory of the double pushout (DPO) approach to graph rewriting. However, so far those same notions were missing for DPO rewriting extended with borrowed contexts (DPOBC), a formalism used for equipping DPO derivations with labels and introduced for modeling open systems that interact with the environment. In this work we propose the definition of parallel and sequential independence for dpobc rewriting, and we prove that these novel notions allow generalizing the Church-Rosser and parallelism theorems holding for DPO rewriting. Most importantly, we show that the DPOBC version of these theorems still guarantees the local confluence and the parallel execution of pairs of independent DPOBC derivations.
Parallel and sequential independence for borrowed contexts
Bonchi, Filippo;GADDUCCI, FABIO;
2008-01-01
Abstract
Parallel and sequential independence are central concepts in the concurrency theory of the double pushout (DPO) approach to graph rewriting. However, so far those same notions were missing for DPO rewriting extended with borrowed contexts (DPOBC), a formalism used for equipping DPO derivations with labels and introduced for modeling open systems that interact with the environment. In this work we propose the definition of parallel and sequential independence for dpobc rewriting, and we prove that these novel notions allow generalizing the Church-Rosser and parallelism theorems holding for DPO rewriting. Most importantly, we show that the DPOBC version of these theorems still guarantees the local confluence and the parallel execution of pairs of independent DPOBC derivations.File | Dimensione | Formato | |
---|---|---|---|
icgt2008Pippo.pdf
solo utenti autorizzati
Tipologia:
Versione finale editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
839.9 kB
Formato
Adobe PDF
|
839.9 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.