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.
