Skip to content
Show report in:

UMINF 14.04

Contextual Hyperedge Replacement

Contextual hyperedge-replacement grammars (contextual grammars, for short) are an extension of hyperedge replacement grammars. They have recently been proposed as a grammatical method for capturing the structure of object-oriented programs, thus serving as an alternative to the use of meta-models like UML class diagrams in model-driven software design.

In this paper, we study the properties of contextual grammars. Even though these grammars are not context-free, one can show that they inherit several of the nice properties of hyperedge replacement grammars. In particular, they possess useful normal forms and their membership problem is in NP.


graph grammar, hyperedge replacement, context, contextual grammar


Frank Drewes and Berthold Hoffmann

Back Edit this report
Entry responsible: Frank Drewes

Page Responsible: Frank Drewes