Conflict Detection for Graph Transformation with Negative Application Conditions

Abstract. This paper introduces a new theory needed for the purpose of conflict detection for graph transformation with negative application conditions (NACs). Main results are the formulation of a conflict no-tion for graph transformation with NACs and a conflict characterization derived from it. A critical pair definition is introduced and complete-ness of the set of all critical pairs is shown. This means that for each conflict, occuring in a graph transformation system with NACs, there exists a critical pair expressing the same conflict in a minimal context. Moreover a necessary and sufficient condition is presented for parallel independence of graph transformation systems with NACs. In order to facilitate the implementation of the critical pair construction for a graph transformation system with NACs a correct construction is formulated. Finally, it is discussed how to continue with the development of conflict detection and analysis techniques in the near future.