A General Framework for Types in Graph Rewriting


Barbara König. A general framework for types in graph rewriting. Acta Informatica, 42(4-5):349–388, 2005.


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.

Suggested BibTeX entry:

    author = {Barbara K{\"o}nig},
    journal = {Acta Informatica},
    number = {4-5},
    pages = {349--388},
    title = {A General Framework for Types in Graph Rewriting},
    volume = {42},
    year = {2005}

Conference versionThis work is not available online here.
© University of Duisburg-Essen, Theoretical Computer Science group