| ROA: | 968 |
| Title: | Evaluating the complexity of Optimality Theory |
| Authors: | Jeffrey Heinz, Gregory Kobele, Jason Riggle |
| Comment: | This is essentially identical to the LI version with a few formatting changes. |
| Length: | 12 |
| Abstract: | Idsardi (2006) claims that Optimality Theory (OT; Prince and Smolensky (1993/2004) is "in general computationally intractable" on the basis of a proof adapted from Eisner (1997). We take issue with this conclusion on two grounds. First, the intractability result holds only in cases where the constraint set is not fixed in advance (contra usual definitions of OT) and second, the result crucially depends on a particular representation of OT grammars. We show that there is an alternative representation of OT grammars that allows for efficient computation of optimal surface forms and provides deeper insight into the sources of complexity of Optimality Theory. We conclude that it is a mistake to reject Optimality Theory on the grounds that it is computationally intractable. |
| Type: | Paper/tech report |
| Area/Keywords: | Phonology,Computation,Formal Analysis |
| Article: | Version 1
|
