Accession Number : AD0772130

Title :   On Traversing Properties of Array Automata.

Descriptive Note : Technical rept.,

Corporate Author : MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER

Personal Author(s) : Shah, Anupam N.

Report Date : NOV 1973

Pagination or Media Count : 138

Abstract : The purpose of the report is to study the pattern traversal power of various two-dimensional automation models. It is shown that traversing a pattern is equivalent to accepting a pattern that has at least one point with a certain local property. On the other hand, the existence of an automaton that halts after traversing a pattern is equivalent to the existence of an automaton that accepts a pattern having no point with a certain local property. It is proved that there is no FSAA (finite state array automaton) that halts after traversing an arbitrary pattern, though there exists an FSAA that traverses simply connected patterns.

Descriptors :   *PATTERN RECOGNITION, *PICTURES, AUTOMATA, TWO DIMENSIONAL, COMPUTERS, GRAPHICS, MATHEMATICAL LOGIC, ARRAYS, THEOREMS.

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE