TY  - JOUR
A1  - Lambers, Leen
A1  - Orejas, Fernando
T1  - Transformation rules with nested application conditions
BT  - critical pairs, initial conflicts & minimality
JF  - Theoretical computer science
N2  - Recently, initial conflicts were introduced in the framework of M-adhesive categories as an important optimization of critical pairs. In particular, they represent a proper subset such that each conflict is represented in a minimal context by a unique initial one. The theory of critical pairs has been extended in the framework of M-adhesive categories to rules with nested application conditions (ACs), restricting the applicability of a rule and generalizing the well-known negative application conditions. A notion of initial conflicts for rules with ACs does not exist yet. 

In this paper, on the one hand, we extend the theory of initial conflicts in the framework of M-adhesive categories to transformation rules with ACs. They represent a proper subset again of critical pairs for rules with ACs, and represent each conflict in a minimal context uniquely. They are moreover symbolic because we can show that in general no finite and complete set of conflicts for rules with ACs exists. On the other hand, we show that critical pairs are minimally M-complete, whereas initial conflicts are minimally complete. Finally, we introduce important special cases of rules with ACs for which we can obtain finite, minimally (M-)complete sets of conflicts.
KW  - Graph transformation
KW  - Critical pairs
KW  - Initial conflicts
KW  - Application
KW  - conditions
Y1  - 2021
U6  - https://doi.org/10.1016/j.tcs.2021.07.023
SN  - 0304-3975
SN  - 1879-2294
VL  - 884
SP  - 44
EP  - 67
PB  - Elsevier
CY  - Amsterdam
ER  -