|
Congruences for Contextual Graph-Rewriting
Vladimiro Sassone
June 2004 |
Abstract:
We introduce a comprehensive operational semantic theory of
graph rewriting. The central idea is recasting rewriting frameworks as Leifer
and Milner's reactive systems. Consequently, graph rewriting systems are
associated with canonical labelled transition systems, on which bisimulation
equivalence is a congruence with respect to arbitrary graph contexts (cospans
of graphs). This construction is derived from a more general theorem of much
wider applicability. Expressed in abstract categorical terms, the central
technical contribution of the paper is the construction of groupoidal
relative pushouts, introduced and developed by the authors in recent work, in
suitable cospan categories over arbitrary adhesive categories. As a
consequence, we both generalise and shed light on rewriting via borrowed
contexts due to Ehrig and König.
Available as PostScript, PDF. |