Cellular Graph Acceptors, 2.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1977
- Accession Number
- ADA050360
Entities
People
- Angela Wu
Organizations
- University of Maryland