Array Automata and Array Grammars, 2.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1971
- Accession Number
- AD0739581
Entities
People
- Azriel Rosenfeld
- David L. Milgram
Organizations
- University of Maryland