A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions (Q1920234)

We consider derivation trees in apex NLC graph languages. We show that for every graph \(H\) in arbitrary apex NLC graph language, a decomposition tree of \(H\) can be constructed from a derivation tree of \(H\). We also show that there exists a hierarchy in the class of apex NLC graph languages: for all \(k\) \((1\leq k)\) \(N_k\) is a proper subset of \(N_{k+1}\), where \(N_k\) denotes the class of graph languages generated by apex NLC graph grammars \(G\) such that the maximal for the number of nonterminal nodes in the start graph and the right-hand sides of productions in \(G\), is at most \(k\).