On the essence and initiality of conflicts inM-adhesive transformation systems

Understanding conflicts between transformation steps and rules is an important topic in algebraic graph transformation. A conflict occurs when two transformation steps are not parallel independent, that is, when after applying one of them the other can no longer occur. A static analysis technique called Critical Pair Analysis allows the detection of all potential conflicts between pairs of rules, by enumerating Critical Pairs. Since these are often too numerous for even simple rules, finding appropriate subsets of critical pairs is the topic of ongoing research. We contribute to this thread by proposing a new characterization of the root causes of conflicts, called “conflict essences”, exploiting a recently proposed characterization of parallel independence. Furthermore we show that conflict essences are precise as the “conflict reasons” previously proposed, and that they uniquely determine the so-called “initial conflicts”, an appropriate subset of critical pairs, under relatively mild assumptions the underlying category. Finally, we show that several M-adhesive categories of interest have the necessary properties for our results to hold, including typed, attributed and symbolic graphs. While our results are formulated for conflicts, they are directly applicatible to dependencies in M-adhesive transformation systems.