[Author Login]
Title:Guarded Optimalism
Authors:Andras Kornai
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.
Type:Paper/tech report
Area/Keywords:Formal Analysis,Computation
Article:Version 1