Computer Science – Computation and Language
Scientific paper
2001-02-22
Jason Eisner, Lauri Karttunen and Alain Theriault (eds.), Finite-State Phonology: Proceedings of the 5th Workshop of the ACL S
Computer Science
Computation and Language
12 pages, online proceedings version (small corrections and clarifications to printed version)
Scientific paper
We 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.
No associations
LandOfFree
Easy and Hard Constraint Ranking in OT: Algorithms and Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Easy and Hard Constraint Ranking in OT: Algorithms and Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Easy and Hard Constraint Ranking in OT: Algorithms and Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-726535