author: Ruud Welling
title: Conflict Detection and Analysis for Single-Pushout High-Level Replacement
keywords:
topics: Algorithms and Data Structures , Graphs
committee: Arend Rensink ,
Jan Kuper ,
Peter van Rossum
started: September 2013
end: February 2014

Description

Graph rules describe changes to a graph structure, in a declarative way. Two rules are dependent if one creates or deletes part of a graph structure that the other relies on.

For the purpose of analysing the effect of a set of graph rules, it is of great advantage to detect such dependencies, and if there are any, to test for confluence of the conflicting rules. For that reason, this problem has been studied and theoretical results have been obtained that show how to do dependency and confluence detection for a large class of graph rules.

The graph transformation enging GROOVE, developed at FMT as an open-source tool in Java, supports a very rich class of rules, including but not limited to those for which the aforementioned theoretical results hold. This assignment involves designing and implementing algorithms (as an extension to GROOVE) for the existing kinds of dependency and confluence detection, and extending these to the full set of GROOVE rules.

 

 

Additional Resources

  1. The paper