Copyright Information
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other
copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying
this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without
the explicit permission of the copyright holder.
Sensoria Bibliography Site Parallel and Sequential Independence for Borrowed Contexts
Filippo Bonchi, Fabio Gadducci, Tobias Heindel
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.