Certifying Rule-Based Models using Graph Transformation

Many systems exhibit rule-based behavior that can be modeled very well by means of graph transformation. In this thesis, a new graph transformation theory is introduced for a more expressive kind of graph transformation than the usual one. This kind of graph transformation not only allows positive pre- and post-conditions to be expressed in rules, but also allows so-called negative application conditions. Present analysis techniques are extended for this more expressive kind of graph transformation. These techniques allow, amongst other things, the static detection of potential conflicts and causal dependencies between transformations, and the detection of local confluence in cases of conflicts. For this purpose, the theory of critical pairs is extended. Moreover, new kinds of analysis techniques are introduced and present techniques are improved. One new technique enables, for example, the static analysis of applicability (resp. non-applicability) of rule sequences. The main part of the newly developed theory in this thesis does not only apply to graph transformation. In addition, it is formulated in the more abstract adhesive high-level-transformation framework. Consequently, the analysis techniques can be applied not only to graphs, but also to other complex structures such as, for example, Petri nets and attributed graphs. Finally, a general road map is presented leading to the certification of a selection of properties in rule-based models. The certification, based on graph transformation analysis techniques, is illustrated by a case study of an elevator control system. Moreover, the current tool support for certification of rule-based models using graph transformation provided by AGG is outlined.