
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