<OT> New Posting: ROA-838

[roa at ruccs.rutgers.edu]

ROA 838-0606

Is OT NP-hard?

Andras Kornai <andras at kornai.com>

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


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.


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

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