Boundary NLC graph grammars - basic definitions, normal forms, and complexity.

*(English)*Zbl 0608.68060Graph grammars generalize the standard phrase structure grammars in that the rewriting is done in graphs rather than in strings. Such a rewriting consists of replacing a subgraph (of a given graph) by another graph. Interesting issues in this area are (a) finding appropriate classes of grammars that generate interesting classes of graphs, (b) parsing, and (c) complexity of various problems.

One of the most widely studied classes of graph grammars are the node label controlled (NLC) grammars introduced by D.Janssens and G. Rozenberg [Inf. Sci. 20, 191-216 (1980; Zbl 0452.68073)]. In this paper the authors introduce a restricted class of NLC grammars called boundary NLC (BNLC) grammars. They show that BNLC grammars are indeed weaker than NLC grammars but still powerful enough to be able to generate interesting classes of graphs. Various applications are discussed and it is shown that the membership problem for BNLC languages for connected graphs of bounded degree is solvable in deterministic polynomial time.

One of the most widely studied classes of graph grammars are the node label controlled (NLC) grammars introduced by D.Janssens and G. Rozenberg [Inf. Sci. 20, 191-216 (1980; Zbl 0452.68073)]. In this paper the authors introduce a restricted class of NLC grammars called boundary NLC (BNLC) grammars. They show that BNLC grammars are indeed weaker than NLC grammars but still powerful enough to be able to generate interesting classes of graphs. Various applications are discussed and it is shown that the membership problem for BNLC languages for connected graphs of bounded degree is solvable in deterministic polynomial time.

Reviewer: G.Slutzki