Context-free graph languages of bounded degree are generated by apex graph grammars (Q1338891): Difference between revisions

The apex graph grammars generate precisely the context-free graph languages of bounded degree, independently of whether one considers hyperedge replacement systems or (boundary or confluent) NLC or edNCE graph grammars. The main feature of apex graph grammars is that nodes cannot be ``passed'' from nonterminal to nonterminal. The proof is based on a normal form result for arbitrary hyperedge replacement systems that forbids ``passing chains''. This generalizes Greibach Normal Form.