Cellular Graph Acceptors, 2.
MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER
Pagination or Media Count:
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
- Theoretical Mathematics