Article (Scientific journals)
Analysis of Permutation Equivalence in M-adhesive Transformation Systems with Negative Application Conditions
Hermann, Frank; Ehrig, Hartmut; Corradini, Andrea
2014In Mathematical Structures in Computer Science, 24 (4-09), p. 1-47
Peer reviewed


Full Text
Publisher postprint (941.36 kB)
Request a copy

The original publication is available at

All documents in ORBilu are protected by a user license.

Send to


Keywords :
graph transformation; permutation equivalence; concurrency
Abstract :
[en] M-adhesive categories provide an abstract framework for a large variety of specification frameworks for modelling distributed and concurrent systems. They extend the well-known frameworks of adhesive and weak adhesive HLR categories and integrate high-level constructs such as attribution as in the case of typed attributed graphs. In the current paper, we investigate -adhesive transformation systems including negative application conditions (NACs) for transformation rules, which are often used in applications. For such systems, we propose an original equivalence on transformation sequences, called permutation equivalence, that is coarser than the classical switch equivalence. We also present a general construction of deterministic processes for -adhesive transformation systems based on subobject transformation systems. As a main result, we show that the process obtained from a transformation sequence identifies its equivalence class of permutation-equivalent transformation sequences. Moreover, we show how the analysis of this process can be reduced to the analysis of the reachability graph of a generated Place/Transition Petri net. This net encodes the dependencies between rule applications of the transformation sequence, including the inhibiting effects of the NACs.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust
Disciplines :
Computer science
Identifiers :
Author, co-author :
Hermann, Frank ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Ehrig, Hartmut;  Technische Universität Berlin, Germany
Corradini, Andrea;  Universita di Pisa, Italy
Language :
Title :
Analysis of Permutation Equivalence in M-adhesive Transformation Systems with Negative Application Conditions
Publication date :
01 August 2014
Journal title :
Mathematical Structures in Computer Science
Publisher :
Cambridge University Press, Cambridge, United Kingdom
Special issue title :
Special Issue 04 (Structure Transformation)
Volume :
Issue :
Pages :
Peer reviewed :
Peer reviewed
Available on ORBilu :
since 12 November 2014


Number of views
69 (10 by Unilu)
Number of downloads
0 (0 by Unilu)

Scopus citations®
Scopus citations®
without self-citations
WoS citations


Similar publications

Contact ORBilu