| ROA: | 841 |
|---|---|
| Title: | Guarded Optimalism |
| Authors: | Andras Kornai |
| Comment: | |
| Length: | 2 |
| 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 |