On the Set of all Subgraphs of the Graphs in a Boundary NLC Graph Language

Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs) which rewrite single nodes only and which establish connections between the embedded graph and neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels in the generated graphs, languages of unlabeled graphs). NLC grammars have been introduced in [JRzl,2] as a basic framework for the mathematical investigation of graph grammars. Other concepts for graph grammars can be found e.g. in [RsM,P,CL,E,N,HbK,JRz] (of course, this is not an exhaustive list). Boundary NLC grammars, BNLC grammars for short, are NLC grammars which are distinguished by the properties that (i) the left-hand side of each production is a nonterminal label and (ii) all the graphs involved (i.e., the axiom graph of the grammar and the right-hand sides of the productions) are such that nodes labeled by nonterminals are never adjacent. BNLC grammars have been investigated in [RzW1,2,3].