Easy and Hard Constraint Ranking in Optimality Theory

Title: Easy and Hard Constraint Ranking in Optimality Theory

Abstract: This research investigates the problem of ranking a set of constraints in Optimality Theory (OT) in a manner consistent with data. The study presents two main findings: (1) a linear-time algorithm for ranking constraints, and (2) a generalization of the algorithm that ranks all possible competitors. The paper also discusses the complexity of these ranking problems and the generation of OT grammars. Finally, the study compares the complexity of these problems in derivational theories, finding them to be P and NP-complete, respectively.

Main Research Question: How efficiently can it find a grammar (if one exists) compatible with a finite set of positive data?

Methodology: The study uses Optimality Theory (OT), a grammatical paradigm that suggests various computational questions. The research presents two versions of the problem: (1) a linear-time algorithm for ranking constraints, and (2) a generalization of the algorithm that ranks all possible competitors.

Results: The research finds that the problem of ranking constraints can be solved efficiently, with a linear-time algorithm that checks if a particular ranking is consistent with given forms. However, the problem of generating OT grammars is found to be OptP-complete, meaning that no polynomial-time algorithm can solve it unless P = NP.

Implications: The study's findings have implications for the learnability of OT-describable languages and the efficiency of finding compatible grammars for a finite set of positive data. The research also contributes to the understanding of the complexity of these problems in derivational theories.

Conclusion: In conclusion, the problem of ranking constraints in Optimality Theory can be solved efficiently, but the problem of generating OT grammars is found to be computationally hard. The study's findings have important implications for the field of linguistics and the understanding of language acquisition and generation.

Link to Article: https://arxiv.org/abs/0102019v1 Authors: arXiv ID: 0102019v1