Transformation Systems with Incremental Negative Application Conditions

In several application areas, Graph Transformation Systems
(GTSs) are equipped with Negative Application Conditions (NACs) that
specify “forbidden contexts”, in which the rules shall not be applied. The
extension to NACs, however, introduces inhibiting effects among transformation steps that are not local in general, causing a severe problem
for a concurrent semantics. In fact, the relation of sequential independence among derivation steps is not invariant under switching, as we
illustrate with an example. We first show that this problem disappears if
the NACs are restricted to beincremental. Next we present an algorithm
that transforms a GTS with arbitrary NACs into one with incremental
NACs only, able to simulate the original GTS. We also show that the two
systems are actually equivalent, under certain assumptions on NACs.