GRAPH PROPERTY RECOGNITION MACHINES,

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)

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1968
Accession Number
AD0682323

Entities

People

  • Herbert S. Shank

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Automata
  • Machines

Fields of Study

  • Computer science

Readers

  • Computer Vision.
  • Mathematical Modeling and Probability Theory.