Back to University of Twente portal
| 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.