| ROA: | 888 |
| Title: | The complexity of hypotheses in Optimality Theory |
| Authors: | Jason Riggle |
| Comment: | |
| Length: | 8 |
| Abstract: | Given a constraint set with k constraints in the framework of Optimality Theory (OT; Prince and Smolensky 1993/2004), what is its capacity as a classification scheme for linguistic data? One useful measure of this capacity is the size of the largest data set (i.e. set of input-output pairs) of which each subset is consistent with a different grammar hypothesis. This metric is known as the Vapnik-Chervonenkis Dimension (VCD) and is a standard complexity measure for concept classes in computational learnability theory. In this work I use the three-valued logic of Prince’s (2002) Elementary Ranking Conditions to show that the VCD of OT with k constraints is k-1. This result establishes that the complexity of Optimality Theory is well behaved as a function of k and that the hardness of OT learning is linear in k for a variety of frameworks that employ probabilistic definitions of learnability. |
| Type: | Paper/tech report |
| Area/Keywords: | Phonology,Computation,Learnability,Formal Analysis |
| Article: | Version 1
|
