Boundary NLC graph grammars - basic definitions, normal forms, and complexity. (English) Zbl 0608.68060

Rozenberg, Grzegorz; Welzl, Emo

Inf. Control 69, 136-167 (1986).

Graph 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.

Reviewer: G.Slutzki

MSC:

68Q45	Formal languages and automata
68Q25	Analysis of algorithms and problem complexity

Keywords:

node label control; graph grammars; BNLC grammars; membership problem; polynomial time

Citations:

Zbl 0452.68073