Operational equivalence of graph transformation systems

Frank Raiser and Thom Frühwirth. Operational equivalence of graph transformation systems. 2009, 6th International Workshop on Constraint Handling Rules (CHR), pages 49-62, Workshop


Graph transformation systems (GTS) provide an important theory for numerous applications. With the growing number of GTS-based applications the comparison of operational equivalence of two GTS becomes an important area of research. This work introduces a notion of operational equivalence for graph transformation systems. The embedding of GTS in constraint handling rules (CHR) provides the basis for a decidable and sufficient criterion for operational equivalence of GTS. It is based on the operational equivalence test for CHR programs. A direct application of adapting this test to GTS allows automatic removal of redundant rules.