R O A
 VIEW ROA 838 
GO

838-0606 
Is OT NP-hard?
Author 
Andras Kornai MetaCarta <andras@kornai.com> [Details]
Length 
1 pp.
Files 
 PDF 53kb
Abstract 


Idsardi (2006) offers a streamlined proof of the thesis that the generation problem of OT is NP-hard. This is a welcome attempt to shed light on this complex matter, but, as we shall demonstrate here, it falls short in justifying the constraints employed in setting up the reduction of OT generation to a known NP-hard problem. The problem is that for a successful encoding dissimilation constraints over an unbounded domain would be required, but these, as we argue, are unattested in the phonologies of natural languages -- the attested constraints (Lyman's Law, Grassman's Law, etc) pertain to a finite (and very small) inventory, namely the nodes in feature geometry.
Keywords 
 OT, generation, NP-hard, dissimilation
Area 
 Formal Analysis, Computation
Type 
 Remark or Reply
 JUMP TO GO  
 Item Display:



R O A