Linear graph grammars: Power and complexity

AbstractA graph grammar is linear if it generates graphs with at most one nonterminal node. Linear graph grammars can simulate nonterminal bounded graph grammars (which generate graphs with a bounded number of nonterminal nodes) and derivation bounded graph grammars. If a linear graph language contains connected graphs of bounded degree only, then it is in NSPACE(logn). These results are shown for graph grammars with neighbourhood controlled embedding and with dynamic edge relabeling (eNCE grammars)