tr-announce

Download

tr-announce@lists.rwth-aachen.de

January 2011

1 participants
1 discussions

2011-04: A Local Greibach Normal Form for Hyperedge Replacement Grammars
by Carsten Fuhs 19 Jan '11

19 Jan '11

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.

1 0