ACL Anthology Network (All About NLP) (beta) The Association Of Computational Linguistics Anthology Network |
ACL ID | P83-1001 |
---|---|
Title | Context-Freeness And The Computer Processing Of Human Languages |
Venue | Annual Meeting of the Association of Computational Linguistics |
Session | Main Conference |
Year | 1983 |
Authors |
|
Context-free grammars, far from having insufficient expressive power for the description of human fan K - uages, may he overly powerful, along three dimen- sions; (i) weak generative capacity: there exists an interesting proper subset of the CFL's, the profligate CFL's, within which no human language appears to fall; (2) strong generative capacity: human languages can be appropriately described in terms of a proper subset of the CF-PSG's, namely those with the ECPO property; (3) time complexity: the recent controversy about the importance of a low deterministic polynomial time bound on the recognition problem for human languages is mis- directed, since an appropriately restrictive theory would guarantee even more, namely a linear bound.