Lars Fritsche ; Alexander Lauer ; Maximilian Kratz ; Andy Schürr ; Gabriele Taentzer - Using weakest application conditions to rank graph transformations for graph repair

lmcs:15117 - Logical Methods in Computer Science, February 27, 2026, Volume 22, Issue 1 - https://doi.org/10.46298/lmcs-22(1:10)2026
Using weakest application conditions to rank graph transformations for graph repairArticle

Authors: Lars Fritsche ; Alexander Lauer ; Maximilian Kratz ; Andy Schürr ; Gabriele Taentzer

    When using graphs and graph transformations to model systems, consistency is an important concern. While consistency has primarily been viewed as a binary property, i.e., a graph is consistent or inconsistent with respect to a set of constraints, recent work has presented an approach to consistency as a graduated property. This allows living with inconsistencies for a while and repairing them when necessary. For repairing inconsistencies in a graph, we use graph transformation rules with so-called {\em impairment-indicating and repair-indicating application conditions} to understand how much repair gain certain rule applications would bring. Both types of conditions can be derived from given graph constraints. Our main theorem shows that the difference between the number of actual constraint violations before and after a graph transformation step can be characterised by the difference between the numbers of violated impairment-indicating and repair-indicating application conditions. This theory forms the basis for algorithms with look-ahead that rank graph transformations according to their potential for graph repair. An evaluation shows that graph repair can be well-supported by rules with these new types of application conditions in terms of effectiveness and scalability.


    Volume: Volume 22, Issue 1
    Published on: February 27, 2026
    Accepted on: December 4, 2025
    Submitted on: January 22, 2025
    Keywords: Software Engineering