## Graph property recognition machinesHerbert S. Shank, Cornell University. Center for Applied Mathematics, United States. Air Force. Office of Scientific Research A study is presented of machines that accept, as inputs, finite connected embedded graphs. These are, roughly, Turing machines in which the Turing tape is replaced by such a graph. Relations of such machines to linear bounded automata are discussed. A description is given of a machine that identifies the parity of the number of maximal trees of a planar graph input, together with a proof that it works. (Author). |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Common terms and phrases

AFOSR agenciea may obtain automata are discussed Automata Theory automaton cocycle connected embedded graphs connected graph CONTRACT OR GRANT CORNELL UNIVERSITY edge is occupied edge whose symbol edges of G Enter finite connected embedded finite set graph property recognition H is marked Hamilton cycle identifies the parity indeterminate belonging initial edge input graph KEY WORDS leftmost edge marked leftmost unmarked edge Lemma linearly bounded machine that identifies machines that accept machines to linear mark a component maximal subforest maximal trees modulo number of edges number of maximal NUMBER OF PAGES NUMBER OF REFERENCES o2 is printed obtain copies occupied exactly once planar graph input presented of machines PROJECT NUMBER Proof property recognition machine reading head moves reading head returns Recognition Graph Theory report number report title returns to bQ symbol already printed tape is replaced tip vertex TOTAL NUMBER Turing machines Turing tape vertex is already xl Xk