Paper: Polynomial Learnability And Locality Of Formal Grammars

ACL ID P88-1028
Title Polynomial Learnability And Locality Of Formal Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1988
Authors
  • Naoki Abe (University of Pennsylvania, Philadelphia PA)

We apply a complexity theoretic notion of feasible learnability called "polynomial learnabillty" to the eval- uation of grammatical formalisms for linguistic descrip- tion. We show that a novel, nontriviai constraint on the degree of ~locMity" of grammars allows not only con- text free languages but also a rich d~s of mildy context sensitive languages to be polynomiaily learnable. We discuss possible implications, of this result t O the theory of naturai language acquisition.