Restrictions on NLC graph grammars
type: Item
instance of: scholarly article
title: Restrictions on NLC graph grammars
zbMATH Open document ID: 0566.68062
DOI: 10.1016/0304-3975(84)90135-X
author: Michael Main
author: Andrzej Ehrenfeucht
author: Grzegorz Rozenberg
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: 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.
reviewed by: Andrea Maggiolo-Schettini
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3903988
zbMATH Keywords: node label controlled grammars
zbMATH Keywords: normal form
zbMATH Keywords: connection relation
zbMATH Keywords: reduction of generating power
MaRDI profile type: Publication
cites work: On certain formal properties of grammars
cites work: A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
cites work: Q5592246
cites work: On the structure of node-label-controlled graph languages
cites work: Restrictions, extensions, and variations of NLC grammars
cites work: Decision problems for node label controlled graph grammars
cites work: A characterization of context-free string languages by directed node- label controlled graph grammars
cites work: Graph grammars with neighbourhood-controlled embedding
cites work: Q3049830
cites work: Deriving graphs from graphs by applying a production
cites work: Q5678435
description: scientific article; zbMATH DE number 3903988