A Note on Scattered Context Grammars.
Abstract
Scattered context grammars can be regarded as web grammars in which the web is the transitive closure of string. It is an open question whether such grammars are strictly weaker than context-sensitive grammars. The report shows that if 'negative context' is allowed, they are as strong as context-sensitive grammars. Negative context alone appears to be comparable in power to (positive) scattered context, but it has not yet been shown that negative context grammars are strictly weaker than context-sensitive grammars. Unordered (positive or negative) scattered context is apparently even weaker, though still stronger than context-free; in web grammar terms, it corresponds to using the complete (undirected) web. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1971
- Accession Number
- AD0724310
Entities
People
- Azriel Rosenfeld
- David L. Milgram
Organizations
- University of Maryland