Permutation Equivalence of DPO Derivations with Negative Application Conditions based on Subobject Transformation Systems

Abstract

Switch equivalence for transformation systems has been successfully used in many domains for the analysis of concurrent behaviour. When using graph transformation as modelling framework for these systems, the concept of negative application conditions (NACs) is widely used - in particular for the specification of operational semantics.
In this paper we show that switch equivalence can be improved essentially for the analysis of systems with NACs by our new concept of permutation equivalence.

Two derivations respecting all NACs are called permutation-equivalent, if they are switch-equivalent disregarding the NACs. In fact, there are permutation-equivalent derivations which are not switch-equivalent with NACs.

As main result of the paper, we solve the following problem:
Given a derivation with NACs, we can efficiently derive all permutation-equivalent derivations to the given one by static analysis. The results are based on extended techniques for subobject transformation systems, which have been introduced recently.