Restrictions on NLC graph grammars (Q1059402)

An NCL (Node Label Controlled) grammar has productions of the type \(X\to \alpha\) where X is a (nonterminal) label and \(\alpha\) is a graph. The daughter graph can be replaced for a mother node labelled X. Conclusions with the neighborhood of the mother node are established using a connection relation. The paper examines restrictions on NLC grammars similar to the Chomsky or Greibach normal form for context-free string grammars. While any context- free language can be generated by a grammar whose productions have length \(1\leq 2\), the restriction of NLC grammar productions to graphs with at most k nodes (with \(k\geq 2)\) reduces the generating power of NCL grammars. If the right side of a production is restricted to contain at least one terminal-labelled node the generating power of NCL grammar is again reduced. Finally the paper deals with restrictions on the connection relation. Functions, inverse functional and symmetric connection relations are considered for the use of alphabets of two or more letters and a reduction of generating power with respect to general NLC grammars is shown. The power of functional, inverse functional and symmetric grammars for a one-letter terminal alphabet, how the restricted classes of languages differ from arbitrary NLC languages, whether useful restrictions do exist which do not reduce the generating power are open problems.