@article{hao-2024-universal,
    title = "Universal Generation for {O}ptimality {T}heory Is {PSPACE}-Complete",
    author = "Hao, Sophie",
    journal = "Computational Linguistics",
    volume = "50",
    number = "1",
    month = mar,
    year = "2024",
    address = "Cambridge, MA",
    publisher = "MIT Press",
    url = "https://preview.aclanthology.org/fix-sig-urls/2024.cl-1.4/",
    doi = "10.1162/coli_a_00494",
    pages = "83--117",
    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 {\ensuremath{\neq}} 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."
}