Accession Number:

AD0724310

Title:

A Note on Scattered Context Grammars.

Descriptive Note:

Technical rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER

Personal Author(s):

Report Date:

1971-03-01

Pagination or Media Count:

16.0

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

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE