Embedding and Confluence of Graph Transformations with Negative Application Conditions

Lambers, Leen; Ehrig, Hartmut; Prange, Ulrike; Orejas, Fernando

by Leen Lambers, Hartmut Ehrig, Ulrike Prange, Fernando Orejas

Abstract:

The goal of this paper is the generalization of embedding and confluence results for graph transformation systems to transformation systems with negative application conditions (NACs). These conditions restrict the application of a rule by expressing that a specific structure must not be present before or after applying the rule to a certain context. Such a condition influences each rule application and transformation and therefore changes significantly the properties of the transformation system. This behavior modification is reflected by the generalization of the Embedding Theorem and the Critical Pair Lemma or Local Confluence Theorem, formulated already for graph transformation systems without negative application conditions. The results hold for adhesive high-level replacement systems with NACs and are formulated in this paper for the instantiation to double-pushout graph transformation systems with NACs. All constructions and results are explained on a running example.

Reference:

Embedding and Confluence of Graph Transformations with Negative Application Conditions (Leen Lambers, Hartmut Ehrig, Ulrike Prange, Fernando Orejas), In Proc. International Conference on Graph Transformation (ICGT'08) (H. Ehrig, Reiko Heckel, Grzegorz Rozenberg, Gabriele Taentzer, eds.), Springer, volume 5214, 2008.

Bibtex Entry:

@InProceedings{LEPO08,
AUTHOR = {Lambers, Leen and Ehrig, Hartmut and Prange, Ulrike and Orejas, Fernando},
TITLE = {{Embedding and Confluence of Graph Transformations with Negative Application Conditions}},
YEAR = {2008},
BOOKTITLE = {Proc. International Conference on Graph Transformation (ICGT'08)},
VOLUME = {5214},
PAGES = {162--177},
EDITOR = {Ehrig, H. and Heckel, Reiko and Rozenberg, Grzegorz and Taentzer, Gabriele},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Heidelberg},
PUBLISHER = {Springer},
PDF = {uploads/pdf/LEPO08_confluenceWithNACs.pdf},
OPTacc_pdf = {},
ABSTRACT = {The goal of this paper is the generalization of embedding and confluence results for graph transformation systems to transformation systems with negative application conditions (NACs). These conditions restrict the application of a rule by expressing that a specific structure must not be present before or after applying the rule to a certain context. Such a condition influences each rule application and transformation and therefore changes significantly the properties of the transformation system. This behavior modification is reflected by the generalization of the Embedding Theorem and the Critical Pair Lemma or Local Confluence Theorem, formulated already for graph transformation systems without negative application conditions. The results hold for adhesive high-level replacement systems with NACs and are formulated in this paper for the instantiation to double-pushout graph transformation systems with NACs. All constructions and results are explained on a running example.}
}