R O A
 VIEW ROA 841 
GO

841-0606 
Guarded Optimalism
Author 
Andras Kornai MetaCarta <andras@kornai.com> [Details]
Length 
2 pp.
Files 
 PDF 66kb
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.
Keywords 
 OT, generation, NP-hard, dissimilation
Area 
 Formal Analysis, Computation
Type 
 Remark or Reply
 JUMP TO GO  
 Item Display:



R O A