RECOGNITION OF TOPOLOGICAL INVARIANTS BY ITERATIVE ARRAYS.
Abstract
A study is made of the recognition and transformation of figures by iterative arrays of finite state automata. A figure is a finite rectangular two-dimensional array of symbols. The iterative arrays considered are also finite, rectangular, and two-dimensional. The automata comprising any given array are called cells and are assumed to be isomorphic and to operate synchronously with the state of a cell at time t + 1 being a function of the states of it and its four nearest neighbors at time t. At time t = 0 each cell is placed in one of a fixed number of initial states. The pattern of initial states thus introduced represents the figure to be processed. The resulting sequence of array states represents a computation based on the input figure. If one waits for a specially designated cell to indicate acceptance or rejection of the figure, the array is said to be working on a recognition problem. If one waits for the arrays to come to a stable configuration representing an output figure, the array is said to be working on a transformation problem. In addition to the formal results, several open questions are presented and some iterative programming techniques are considered. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 24, 1969
- Accession Number
- AD0699502
Entities
People
- Wendell Terry Beyer
Organizations
- Massachusetts Institute of Technology