Abstract
This article shows that the universal generation problem for Optimality Theory (OT) is PSPACE-complete. While prior work has shown that universal generation is at least NP-hard and at most EXPSPACE-hard, our results place universal generation in between those two classes, assuming that NP ≠ PSPACE. We additionally show that when the number of constraints is bounded in advance, universal generation is at least NL-hard and at most NPNP-hard. Our proofs rely on a close connection between OT and the intersection non-emptiness problem for finite automata, which is PSPACE-complete in general and NL-complete when the number of automata is bounded. Our analysis shows that constraint interaction is the main contributor to the complexity of OT: The ability to factor transformations into simple, interacting constraints allows OT to furnish compact descriptions of intricate phonological phenomena.- Anthology ID:
- 2024.cl-1.4
- Volume:
- Computational Linguistics, Volume 50, Issue 1 - March 2024
- Month:
- March
- Year:
- 2024
- Address:
- Cambridge, MA
- Venue:
- CL
- SIG:
- Publisher:
- MIT Press
- Note:
- Pages:
- 83–117
- Language:
- URL:
- https://aclanthology.org/2024.cl-1.4
- DOI:
- 10.1162/coli_a_00494
- Cite (ACL):
- Sophie Hao. 2024. Universal Generation for Optimality Theory Is PSPACE-Complete. Computational Linguistics, 50(1):83–117.
- Cite (Informal):
- Universal Generation for Optimality Theory Is PSPACE-Complete (Hao, CL 2024)
- PDF:
- https://preview.aclanthology.org/dois-2013-emnlp/2024.cl-1.4.pdf