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

  • 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. TwoSwitch 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 techniquesshow moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author: Frank Hermann
URN:urn:nbn:de:kobv:83-opus-31239
ISBN:1863-2122
Series (Serial Number):Electronic Communications of the EASST- ECEASST (16/05)
Document Type:Arbeitspapier/Research Paper
Language:English
Date of Publication (online):2011/08/10
Publishing Institution:Technische Universität Berlin
Release Date:2011/08/10
Tag:Adhesive Categories; Graph Transformation; Negative Application Conditions; Process Analysis; Subobject Transformation Systems
Note:
http://journal.ub.tu-berlin.de/eceasst/article/view/251
Institutes:Institut für Softwaretechnik und Theoretische Informatik
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Collection:Volume 16 (2009): International Conference on Graph Transformation 2008 - Doctoral Symposium
Licence (German):License Logo CC BY-NC-SA: Creative Commons-Lizenz: Namensnennung, nicht kommerziell, Weitergabe zu gleichen Bedingungen