An axiomatic definition of context-free rewriting and its application to NLC graph grammars (Q1102759)

The paper deals with graph grammars. An abstract notion of context-free grammar over an arbitrary class of combinatorial objects is introduced. The node-label controlled (NLC) graph grammars, which have been defined and investigated by Janssens, Rozenberg and Welzl, are studied from this point of view. A monadic second-order theory of context-free NLC sets of graphs appropriate for expressing properties of graphs is introduced. It is shown that this theory is decidable. Some decidability results of graph grammars obtained by other authors are simple consequences of this result.