<OT> New Posting: ROA-968

[roa at ruccs.rutgers.edu]

ROA 968-0508

Evaluating the complexity of Optimality Theory

Jason Riggle <jriggle at uchicago.edu>
Apollo Hogan <apollo at math.berkeley.edu>

Direct link: http://roa.rutgers.edu/view.php3?roa=968


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 computation
ally intractable.

Comments: This is essentially identical to the LI version with a few formatting changes.
Keywords: optimality theory, computational complexity, generation problem
Areas: Phonology,Computation,Formal Analysis
Type: Journal Article

Direct link: http://roa.rutgers.edu/view.php3?roa=968