direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Publications Prof. Hartmut Ehrig (TFS)

Efficient Conflict Detection in Graph Transformation Systems by Essential Critical Pairs
Zitatschlüssel LEO08
Autor Lambers, L. and Ehrig, H. and Orejas, F.
Buchtitel Proc. International Workshop on Graph Transformation and Visual Modeling Techniques (GTVMT'06)
Seiten 17–26
Jahr 2008
Ort Vienna, Austria
Adresse Amsterdam
Jahrgang 211
Verlag Elsevier Science
Zusammenfassung The well-known notion of critical pairs already allows a static conflict detection, which is important for all kinds of applications and already implemented in AGG. Unfortunately the standard construction is not very efficient. This paper introduces the new concept of essential critical pairs allowing a more efficient conflict detection. This is based on a new conflict characterization, which determines for each conflict occuring between the rules of the system the exact conflict reason. This new notion of conflict reason leads us to an optimization of conflict detection. Efficiency is obtained because the set of essential critical pairs is a proper subset of all critical pairs of the system and therefore the set of representative conflicts to be computed statically diminishes. It is shown that for each conflict in the system, there exists an essential critical pair representing it. Moreover each essential critical pair possesses a unique conflict reason and thus represents each conflict not only in a minimal, but also in a unique way. Main new results presented in this paper are a characterization of conflicts, completeness and uniqueness of essential critical pairs and a local confluence lemma based on essential critical pairs. The theory of essential critical pairs is the basis to develop and implement a more efficient conflict detection algorithm in the near future.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe