Paper: Context-Freeness And The Computer Processing Of Human Languages

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.