@TechReport{LEO06b-TR,
AUTHOR = {Lambers, Leen and Ehrig, Hartmut and Orejas, Fernando},
TITLE = {{Efficient Conflict Detection in Graph Transformation Systems by Essential Critical Pairs}},
YEAR = {2006},
NUMBER = {2006-07},
INSTITUTION = {Technische Universitat Berlin},
URL = {http://iv.tu-berlin.de/TechnBerichte/2006/2006-07.pdf},
OPTacc_url = {},
PDF = {uploads/pdf/LEO06b-TR_2006.pdf},
OPTacc_pdf = {},
ABSTRACT = {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 detec-
tion. 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. Ef-
ficiency 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.}
}