Deriving Bisimulation Congruences in the DPO Approach to Graph ...
Reference
Hartmut Ehrig and Barbara König. Deriving bisimulation congruences in the DPO approach to graph rewriting. Technical Report 01/2004, Universität Stuttgart, 2004.
Abstract
Motivated by recent work on the derivation of labelled transitions and bisimulation congruences from unlabelled reaction rules, we show how to solve this problem in the DPO (double-pushout) approach to graph rewriting. Unlike in previous approaches, we consider graphs as objects, instead of arrows, of the category under consideration. This allows us to present a very simple way of deriving labelled transitions (called rewriting steps with borrowed context) which smoothly integrates with the DPO approach, has a very constructive nature and requires only a minimum of category theory. The core part of this paper is the proof sketch that the bisimilarity based on rewriting with borrowed contexts is a congruence relation.
Suggested BibTeX entry:
@techreport{EK04a,
author = {Hartmut Ehrig and Barbara K{\"o}nig},
institution = {Universit{\"a}t Stuttgart},
number = {01/2004},
title = {Deriving Bisimulation Congruences in the {DPO} Approach to Graph Rewriting},
year = {2004}
}
