Polynomial learnability and locality of formal grammars
Naoki Abe · 1988
We apply a complexity theoretic notion of feasible learnability called "polynomial learnability" to the evaluation of grammatical formalisms for linguistic description. We show that a novel, nontrivial constraint on the degree of "locality" of grammars allows not only context free languages but also a rich class of mildy context sensitive languages to be polynomially learnable. We discuss possible implications of this result to the theory of natural language acquisition.