@Article{LAMBERS2021,
AUTHOR = {Lambers, Leen and Orejas, Fernando},
TITLE = {{Transformation rules with nested application conditions: Critical pairs, initial conflicts & minimality}},
YEAR = {2021},
JOURNAL = {Theoretical Computer Science},
VOLUME = {884},
PAGES = {44-67},
URL = {https://doi.org/10.1016/j.tcs.2021.07.023},
PDF = {uploads/pdf/LAMBERS2021.pdf},
OPTacc_pdf = {},
ABSTRACT = {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.}
}