Weak Greibach Normal Form for Hyperedge Replacement Grammars

Tikhon Pshenitsyn
(Lomonosov Moscow State University, Russia)

It is known that hyperedge replacement grammars are similar to string context-free grammars in the sense of definitions and properties. Therefore, we expect that there is a generalization of the well-known Greibach normal form from string grammars to hypergraph grammars. Such generalized normal forms are presented in several papers; however, they do not cover a large class of hypergraph languages (e.g. languages consisting of star graphs). In this paper, we introduce a weak Greibach normal form, whose definition corresponds to the lexicalized normal form for string grammars, and prove that every context-free hypergraph language (with nonsubstantial exceptions) can be generated by a grammar in this normal form. The proof presented in this paper generalizes a corresponding one for string grammars with a few more technicalities.

In Berthold Hoffmann and Mark Minas: Proceedings of the Eleventh International Workshop on Graph Computation Models (GCM 2020), Online-Workshop, 24th June 2020, Electronic Proceedings in Theoretical Computer Science 330, pp. 108–125.
Published: 3rd December 2020.

ArXived at: http://dx.doi.org/10.4204/EPTCS.330.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org