Abstract

Adapting arguments from Eisner 1997, 2000, this remark provides a simple proof that the generation problem for Optimality Theory (Prince and Smolensky 2004) is NP-hard. The proof needs only the binary evaluation of constraints and uses only constraints generally employed in the Optimality Theory literature. In contrast, rule-based derivational systems are easily computable, belonging to the class of polynomialtime algorithms, P (Eisner 2000).

pdf

Additional Information

ISSN
1530-9150
Print ISSN
0024-3892
Pages
pp. 271-275
Launched on MUSE
2006-05-22
Open Access
No
Back To Top

This website uses cookies to ensure you get the best experience on our website. Without cookies your experience may not be seamless.