A Normal Form Problem for Unlabeled Boundary NLC Graph Languages

AbstractWe consider an existential problem of a Chomsky-type normal form for unlabeled boundary NLC graph languages. Let G be a boundary NLC graph grammar, maxr(G) be the maximum for the sizes of graphs which are the start graph (axiom) and the right-hand sides of production rules in G, and und(L(G)) is the set of underlying unlabeled graphs which are obtained from graphs in the generated language L(G) by removing the labels. Then it is an open question (Rozenberg and Welzl, 1986, Inform. and Control69, 136-167) whether there exists a positive integer k0 such that there is a boundary NLC graph grammar G with maxr(G) ≤ k0 and L = und(L(G)) for every unlabeled boundary NLC graph language L. We will show that there is an infinite hierarchy in the class of the underlying unlabeled boundary NLC graph languages with respect to the sizes of the graphs appearing in the production rules of the boundary NLC graph grammars that generate the underlying unlabeled boundary NLC graph languages. Finally, we will show that there is no integer k0 satisfying the above conditions, using a pumping lemma for boundary NLC graph languages