Reference : Permutation Equivalence of DPO Derivations with Negative Application Conditions based...
Reports : External report
Engineering, computing & technology : Computer science
Permutation Equivalence of DPO Derivations with Negative Application Conditions based on Subobject Transformation Systems: Long Version
Hermann, Frank mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
TU Berlin, Fak. IV
ISSN 1436-9915
[en] 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.

File(s) associated to this reference

Fulltext file(s):

Open access
tr-2009-10.pdfPublisher postprint683.8 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.