Technischer Bericht TR-2004-01

Ehrig, Hartmut; König, Barbara: Deriving Bisimulation Congruences in the DPO Approach to Graph Rewriting (Long Version).
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2004/01.
30 Seiten, englisch.
CR-Klassif.F.3.2 (Semantics of Programming Languages)
F.4.2 (Grammars and Other Rewriting Systems)
F.3.1 (Specifying and Verifying and Reasoning about Programs)
G.2.2 (Discrete Mathematics Graph Theory)
Keywordsgraph rewriting; graph transformation; bisimulation; transition systems

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.

Volltext und
andere Links
PDF (1084994 Bytes)
PostScript (1833220 Bytes)
Veröffentlichungen der Abteilung SZS
KontaktE-Mail an
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Sichere und Zuverlässige Softwaresysteme
Eingabedatum27. Februar 2004
   Publ. Informatik