The following technical report is available from http://aib.informatik.rwth-aachen.de:

A Local Greibach Normal Form for Hyperedge Replacement Grammars Christina Jansen, Jonathan Heinen, Joost-Pieter Katoen, Thomas Noll AIB 2011-04

Heap-based data structures play an important role in modern programming concepts. However standard verification algorithms cannot cope with infinite state spaces as induced by these structures. A common approach to solve this problem is to apply abstraction techniques. Hyperedge replacement grammars provide a promising technique for heap abstraction as their production rules can be used to partially abstract and concretise heap structures. To support the required concretisations, we introduce a normal form for hyperedge replacement grammars as a generalisation of the Greibach Normal Form for string grammars and the adapted construction.