A flattening approach for attributed type graphs with inheritance in algebraic graph transformation

Authors Christine Natschl├Ąger
Klaus-Dieter Schewe
Editors
Title A flattening approach for attributed type graphs with inheritance in algebraic graph transformation
Type article
Journal Electronic Communications of the EASST
Volume volume 47 Graph Transformation and Visual Modeling Techniques 2012
ISSN 1863-2122
Month July
Year 2013
Pages http://journal.ub.tu-berlin.de/eceasst/issue/view/61
SCCH ID# 1243
Abstract

The algebraic graph transformation approach was initiated in 1973 and supports the rule-based modification of graphs based on pushout constructions. The vertex and edge types used within the rules (or productions) as well as possible inheritance relationships defined between them are specified in the type graph. However, the termination proof can only be accomplished for graph transformation systems without inheritance relationships. Thus, all graph transformation systems with inheritance relationships in the type graph must be flattened. To this end, the algebraic graph transformation approach provides a formal description for how to flatten the type graph as well as a definition of abstract and concrete productions. In this paper, we will extend the definitions to also consider vertices in negative application conditions with finer node types and positive application conditions. Furthermore, we will prove the semantic equivalence of the original and the flattened graph transformation system. The whole flattening algorithm is then implemented in a prototype which supports an abstract or concrete flattening of a given graph transformation system. The prototype is finally evaluated within a case study.