Quarterly (winter, spring, summer, fall)
224 pp. per issue
6 3/4 x 9 1/4
ISSN
0024-3892
E-ISSN
1530-9150
2014 Impact factor:
1.71

Linguistic Inquiry

Spring 2009, Vol. 40, No. 2, Pages 277-288
(doi: 10.1162/ling.2009.40.2.277)
© 2009 Massachusetts Institute of Technology
Evaluating the Complexity of Optimality Theory
Article PDF (80.03 KB)
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 1997a. 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 OT. We conclude that it is a mistake to reject OT on the grounds that it is computationally intractable.