Accession Number:

AD0739581

Title:

Array Automata and Array Grammars, 2.

Descriptive Note:

Technical rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER

Personal Author(s):

Report Date:

1971-09-01

Pagination or Media Count:

18.0

Abstract:

Finite automata having two-dimensional tapes are much less well-behaved than their one-dimensional counterparts. In particular, for such automata, one-way is weaker than two-way, array-bounded is weaker than non-array-bounded, and deterministic is weaker than nondeterministic. It also appears to be difficult to define a natural class of array grammars that is equal in power to any of these types of array automata all of the definitions formulated thus far either have the wrong power or have some degree of artificiality. Author

Subject Categories:

  • Computer Programming and Software
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE