Hierarchical graph transformations with meta-rules

Abstract

This paper is concerned with hierarchical graph models and graph transformation rules, specifically with the problem of transforming a part of graph which may contain subordinated nodes and edges. Meta-rules are proposed as a formal way of representing transformations which remove or duplicate a node along with its contents. The paper discusses the behaviour of meta-rules when applied to different types of hierarchical graphs, possible failure cases, and concludes by introducing a type of hierarchical graphs in which meta-rules can always be successfully expanded.