Isotonic Grammars, Parallel Grammars, and Picture Grammars
Abstract
When one attempts to generalize phrase-structure grammars from strings to arrays, difficulties arise which can be avoided if the grammars are required to be isotonic: in any array rewriting rule, the left and right members are congruent subarrays. Isotonic context-sensitive array rewriting rules are essentially the same as local digital picture processing operations. Since the latter are often applied to pictures in parallel, it is of interest to study (string) grammars which operate in parallel: that is, when a rule is applied to a string, every instance of the left member is replaced by the right member. (Here again, there are difficulties which can be avoided if all rules are isotonic and context-sensitive.) The sets of sentences which such a parallel grammar generates is not the same as the set of sentences which it parses, nor is either of these the same as the set of sentences generated (or parsed) when rules need not be applied in parallel. However, any parallel language is a sequential language and vice versa.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1970
- Accession Number
- AD0708402
Entities
People
- Azriel Rosenfeld
Organizations
- University of Maryland