A General Framework for Types in Graph Rewriting

In: Acta Informatica, Jg. 42 (2005) ; Nr. 4-5, S. 349-388
ISSN: 0001-5903
Zeitschriftenaufsatz / Fach: Informatik
We investigate a general framework which can be instantiated in order to obtain type systems for graph rewriting, allowing us to statically infer behavioural properties of a graph. We describe conditions such as the subject reduction property and compositionality that should be satisfied by such a framework. We present a methodology for proving these conditions, specifically we prove that it is sufficient to show properties that are local to graph transformation rules. In order to show the applicability of this framework, we describe in several case studies how to integrate existing type systems (for the π-calculus and the λ-calculus) and a system for typing acyclic graphs.