On Traversing Properties of Array Automata.
MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER
Pagination or Media Count:
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.