The complexity of graph languages generated by hyperedge replacement (Q2277851)

Hyperedge replacement grammars (HRGs) are a grammatical formalism for generating classes of graphs. The general parsing problem for HRGs is known to be NP-complete. The author analyses the difficulty of HRG parsing and develops certain conditions, on either the grammars or the input graphs, under which the parsing can be done either in polynomial time, or by efficient parallel algorithms.