Accession Number : AD0682323

Title :   GRAPH PROPERTY RECOGNITION MACHINES,

Corporate Author : CORNELL UNIV ITHACA N Y CENTER FOR APPLIED MATHEMATICS

Personal Author(s) : Shank,Herbert S.

Report Date : OCT 1968

Pagination or Media Count : 17

Abstract : 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)

Descriptors :   (*DIGITAL COMPUTERS, PATTERN RECOGNITION), (*PATTERN RECOGNITION, GRAPHICS), AUTOMATA, SET THEORY, SYMBOLS, THEOREMS

Subject Categories : Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE