University of Twente Student Theses

Login

Conflict detection and analysis for single-pushout high-level replacement

Welling, Ruud (2014) Conflict detection and analysis for single-pushout high-level replacement.

[img] PDF
875kB
Abstract:In many graph transformation systems (local) confluence is a desired property. For instance, if graph transformation is used for model transformation, then confluence and termination ensure that the order in which rules are applied does not matter, in other words, the final result will always be the same. In this research we investigate su�cient conditions for local confluence of high-level replacement (HLR) systems. Using the single-pushout high-level replacement approach we de�ne critical pairs (minimal conflicting situations). Our su�cient condition for local confluence is based on the analysis of critical pairs. We provide our proofs on a categorical level, therefore our theory cannot only be applied to the category of graphs: we formulate requirements for the categories for which our theorems hold, and we show that our theory is also applicable to attributed graphs. We also present some of the foundations for confluence analysis for HLR systems with negative application conditions (NACs). In order to show local confluence for a HLR system with NACs we will show that stricter conditions must hold for the critical pairs with NACs (compared to the situation without NACs). We show that HLR systems without NACs are locally confluent. Further analysis of HLR systems with NACs is future work. Our theory has been implemented in the graph transformation tool groove. Using our implementation we can �nd all critical pairs for a graph transformation system, and analyse if these pairs are locally confluent. Using this implementation we have performed some experiments on existing graph transformation systems.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:http://purl.utwente.nl/essays/65031
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page