The Complexity of Learning Principles and Parameters Grammars
This work addresses the computational feasibility of learning formal language classes, which is an incremental contribution to theoretical computer science and linguistics.
The paper investigates models for learning context-free and context-sensitive languages, introducing principled parametric grammars based on psycholinguistics, and presents hardness results showing these grammars are not efficiently learnable under certain conditions unless P = NP or integer factorization is in P.
We investigate models for learning the class of context-free and context-sensitive languages (CFLs and CSLs). We begin with a brief discussion of some early hardness results which show that unrestricted language learning is impossible, and unrestricted CFL learning is computationally infeasible; we then briefly survey the literature on algorithms for learning restricted subclasses of the CFLs. Finally, we introduce a new family of subclasses, the principled parametric context-free grammars (and a corresponding family of principled parametric context-sensitive grammars), which roughly model the "Principles and Parameters" framework in psycholinguistics. We present three hardness results: first, that the PPCFGs are not efficiently learnable given equivalence and membership oracles, second, that the PPCFGs are not efficiently learnable from positive presentations unless P = NP, and third, that the PPCSGs are not efficiently learnable from positive presentations unless integer factorization is in P.