On Traversing Properties of Array Automata.

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.

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1973
Accession Number
AD0772130

Entities

People

  • Anupam N. Shah

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Adaptive Control Systems
  • Adaptive Systems
  • Automata
  • Automation
  • Control Systems
  • Geometry
  • Machines
  • Two Dimensional

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Vision.