Event Structure Semantics for Dynamic Graph Grammars

Roberto Bruni, Hernan Melgratti, Ugo Montanari

Abstract


Dynamic graph grammars (DGGs) are a reflexive extension of Graph Grammars that have been introduced to represent mobile reflexive systems and calculi at a convenient level of abstraction. Persistent graph grammars (PGGs) are a class of graph grammars that admits a fully satisfactory concurrent semantics thanks to the fact that all so-called asymmetric conflicts (between items that are read by some productions and consumed by other) are avoided. In this paper we introduce a slight variant of DGGs, called persistent dynamic graph grammars (PDGGs), that can be encoded in PGGs preserving concurrency. Finally, PDGGs are exploited to define a concurrent semantics for the Join calculus enriched with persistent messaging (if preferred, the latter can be naively seen as dynamic nets with read arcs).

Full Text:

PDF


DOI: http://dx.doi.org/10.14279/tuj.eceasst.2.57

DOI (PDF): http://dx.doi.org/10.14279/tuj.eceasst.2.57.29

Hosted By Universit├Ątsbibliothek TU Berlin.