Accession Number:

ADA050360

Title:

Cellular Graph Acceptors, 2.

Descriptive Note:

Interim rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER

Personal Author(s):

Report Date:

1977-12-01

Pagination or Media Count:

53.0

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

Subject Categories:

  • Cybernetics
  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE