TY - CONF
AB - In this paper the concurrent semantics of double-pushout (DPO) graph rewriting, which is classically defined in terms of shift-equivalence classes of graph derivations, is axiomatised via the construction of a free monoidal bi-category. In contrast to a previous attempt based on 2-categories, the use of bi-categories allows to define rewriting on concrete graphs. Thus, the problem of composition of isomorphism classes of rewriting sequences is avoided. Moreover, as a first step towards the recovery of the full expressive power of the formalism via a purely algebraic description, the concept of disconnected rules is introduced, i.e., rules whose interface graphs are made of disconnected nodes and edges only. It is proved that, under reasonable assumptions, rewriting via disconnected rules enjoys similar concurrency properties like in the classical approach.
AU - Gadducci, Fabio
AU - Heckel, Reiko
AU - Llabrés, Mercé
ID - 7858
T2 - Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK)
TI - A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting
VL - 29
ER -