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) : Rosenfeld,Azriel ; Milgram,David L.

Report Date : SEP 1971

Pagination or Media Count : 18

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)

Descriptors :   (*COMPUTER PROGRAMMING, AUTOMATA), GRAMMARS, ARTIFICIAL INTELLIGENCE, NETWORKS

Subject Categories : Computer Programming and Software
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE