4/03/2004
Pawel Sobocinski (BRICS)
Coinductive Reasoning for Contextual Graph Rewriting

The talk will concern a semantic theory for graph rewriting. The theory is operational, and therefore, lends itself to the application of coinductive principles. The central idea is the recasting of rewriting frameworks as reactive systems with the resulting contextual equivalences.

Specifically, a graph rewriting system is associated with a labelled transition system (LTS), so that the corresponding bisimulation is a congruence with respect to arbitrary graph contexts. These LTSs are derived using a general construction of groupoidal relative pushouts in suitable cospan categories over arbitrary adhesive categories. This general construction shall be presented, together with other possible applications.