Mildly Context-Sensitive Languages

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 …...