The Complexity of Learning in Optimality Theory and Its Implications for the Acquisition of Phonotactics

The consistency problem models language learning as the problem of finding a grammar consistent with finite linguistic data. The subset problem refines that formulation, asking for a consistent grammar that generates a smallest language. This article reviews results concerning the tractability of the consistency problem within Optimality Theory (OT) and shows that the OT subset problem is instead intractable. The subset problem thus needs to be restricted to plausible typologies, and solution algorithms need to take advantage of the additional structure brought about by these typological restrictions. These implications are illustrated with a discussion of the choice between batch and error-driven models of the child’s acquisition of phonotactics.