<OT> New Posting: ROA-841

[roa at ruccs.rutgers.edu]

ROA 841-0606

Guarded Optimalism

Andras Kornai <andras at kornai.com>

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


Abstract:
In this note we offer a reply to Idsardi (2006b) responding to Kornai (2006), where we questioned the strength of the demonstration offered in Idsardi (2006a) that the decision problem whether a particular string is licensed by an OT grammar is NP-hard. We present a simple bound, min(n,p,2^c) for the maximum Hamilton search problem that could be encoded in the grammar, where n is the size of the domain, p is the size of the inventory, and c is the number of constraints operating in parallel, and argue that OT is guarded from computational blow-up by the fact that this number is small. 

Comments: 
Keywords: OT, generation, NP-hard, dissimilation
Areas: Formal Analysis,Computation
Type: Remark or Reply

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