Parallel algorithms for a class of graphs generated recursively (Q582922)

A star graph (G,R) is a kernel graph G and a set of additional pending edges R called legs each having exactly one common vertex with G. The vertices of G are labelled by a terminal and nonterminal symbols. A grammar is given by an axiom star graph \(X_ 0\) with no legs and a set of production \(X\to Y\). Here X is a star graph, whose kernel consists of only one vertex labelled by a nonterminal, and Y is a star graph with the same number of legs as X. The language of graphs defined by such a grammar is the set of all graphs (with only terminal labels) which are derivable from \(X_ 0\) by using the productions. Let \(NC^ i\) be the class of problems coumputable by a parallel random access machine. Then, recognition and parsing of graphs generated by such a grammar is i \(NC^ 2\), and several NP-complete problems are in \(NC^ 1\), if the parsing tree is given.