Easy and Hard Constraint Ranking in OT: Algorithms and Complexity

Simple item page
dc.creatorEisner, Jason
dc.date2001-02-22
dc.date.accessioned2026-07-07T03:16:57Z
dc.date.available2026-07-07T03:16:57Z
dc.descriptionWe consider the problem of ranking a set of OT constraints in a manner consistent with data. We speed up Tesar and Smolensky's RCD algorithm to be linear on the number of constraints. This finds a ranking so each attested form x_i beats or ties a particular competitor y_i. We also generalize RCD so each x_i beats or ties all possible competitors. Alas, this more realistic version of learning has no polynomial algorithm unless P=NP! Indeed, not even generation does. So one cannot improve qualitatively upon brute force: Merely checking that a single (given) ranking is consistent with given forms is coNP-complete if the surface forms are fully observed and Delta_2^p-complete if not. Indeed, OT generation is OptP-complete. As for ranking, determining whether any consistent ranking exists is coNP-hard (but in Delta_2^p) if the forms are fully observed, and Sigma_2^p-complete if not. Finally, we show that generation and ranking are easier in derivational theories: in P, and NP-complete.
dc.description12 pages, online proceedings version (small corrections and clarifications to printed version)
dc.identifierhttps://arxiv.org/abs/cs/0102019
dc.identifierhttp://arxiv.org/abs/cs/0102019
dc.identifierJason Eisner, Lauri Karttunen and Alain Theriault (eds.), Finite-State Phonology: Proceedings of the 5th Workshop of the ACL Special Interest Group in Computational Phonology (SIGPHON), pp. 22-33. Luxembourg, August 2000
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30548
dc.subjectComputation and Language
dc.subjectComputational Complexity
dc.subjectI.2.7; F.2.2
dc.titleEasy and Hard Constraint Ranking in OT: Algorithms and Complexity
dc.typetext

Files

Collections

arXiv