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
Distribution Statement : APPROVED FOR PUBLIC RELEASE