Cellular Graph Acceptors, 2.
Angela Wu · Defense Technical Information Center (DTIC) · 1977
In an earlier report, sequential and parallel acceptors were defined whose languages are sets of d-graphs, i.e., labelled graphs of bounded degree whose arcs at each node are numbered. This report defines graph acceptance by cellular d-graph automata, and gives efficient algorithms for acceptance of various basic types of graphs including cycles, strings, trees, and complete graphs. It presents fast algorithms for constructing a spanning tree of a d-graph and counting the nodes of the tree, and applies these algorithms to the measurement of the radius and area (= number of nodes) of the graph, as well as to detection and counting of occurrences of specific node labels. It also defines acceptance of graphs by sequential d-graph automata, and establishes the equivalence between such automata and web-bounded automata. (Author)