A Flattening Approach for Attributed Type Graphs with Inheritance in Algebraic Graph Transformation

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 in-heritance relationships defined between them are specified in the type graph. How-ever, the termination proof can only be accomplished for graph transformation sys-tems without inheritance relationships. Thus, all graph transformation systems with inheritance relationships in the type graph must be flattened. To this end, the alge-braic 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 ap-plication conditions with finer node types and positive application conditions. Fur-thermore, 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